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$的，只要$\mathrm{\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\ne t$

输出格式:

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

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

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

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

请保证$\mathrm{\forall }i,w_{i,i}=0,\mathrm{\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