strawgoH

题目描述:

众所周知，strawgoH是一所著名的魔法学校。

strawgoH有\(N\)间教室，对于任意两间教室\(u, v\)，有一条有向走廊连接它们，且通过时间为\(w_{u, v}\)，注意不一定有\(w_{u, v} = w_{v, u}\)。

你并不知道经过每条走廊所需要的时间\(w_{u, v}\)是多少，但是你知道，作为一所魔法学校，strawgoH比NJU要高明多了，strawgoH的教室/走廊满足以下两个神奇的性质:

• 路径无关：在strawgoH， 迷路是非常常见的事情。所以对于任意两间教室\(u\)和\(v\)，从\(u\)走到\(v\)的时间是路径无关的。即保证不论你走什么路径（可以包含环），最终所经过的时间只取决于起点和终点是什么。当然这就要求经过某些走廊所需要的时间是负数，但是这又有什么做不到的呢?
• 时间限制：学生们往往要在课间从一间教室赶到另一间教室。strawgoH有\(M\)个课间，第\(i\)个课间里有学生要从教室\(u_i\)走到教室\(v_i\)，strawgoH需要保证你一定能在\(t_i\)时间内走到。

现在你要从教室\(s\)走到教室\(t\)，问在满足以上两个条件的所有可能的情况下，从\(s\)到\(t\)的时间最久可能是多久? (因为第一个性质，这个时间是路径无关的)

或者请判断这个时间其实没有上界。

显然是一定可以从\(s\)走到\(t\)的，只要\(\forall i, j, w_{i, j} = 0\)就行了。

输入格式:

第一行两个整数\(N\)和\(M\)，分别表示教室的数量和课间的数量。

接下来\(M\)行，每行三个整数\(u_i, v_i, t_i\)，表示从\(u_i\)到\(v_i\)的时间小于等于\(t_i\)。

最后一行两个整数\(s\)和\(t\)，表示你要从\(s\)走到\(t\)。

\(2 \le N \le 1000\)

\(0 \le M \le N^2\)

\(1 \le s, t, u_i, v_i \le N\)

\(0 \le t_i \le 10000\)

\(s \neq t\)

输出格式:

如果时间没有上界，请输出一个整数\(-1\)。否则

第一行一个整数表示从\(s\)到\(t\)需要的时间的上界\(d\)。

接下来输出一种方案使得从\(s\)到\(t\)的时间达到上界\(d\)，且符合题目两个要求。

方案共\(N\)行，每行\(N\)个数字，第\(i\)行第\(j\)个数字表示通过连接\(i, j\)的走廊的时间\(w_{i, j}\)。

请保证\(\forall i, w_{i, i} = 0, \forall i, j, |w_{i, j}| \le 10^9\).

如果有多种方案，请输出任意一种。

样例输入:

3 3
1 2 1
2 3 1
1 3 3
1 3

样例输出:

2
0 1 2
-1 0 1
-2 -1 0

提示:

样例2:

inupt

2 0

1 2

output

-1

时间限制: 2000ms
空间限制: 256MB

---

来源: by Massimo