Z国有 N 座城市和 M 条道路。
城市编号为 1 至 N ，道路编号为 1 至 M 。道路 i 是一条从城市 A_i 通往城市 B_i 的**单向**道路，通过这条道路需要 C_i 分钟。
让我们将 f(s, t, k) 定义为以下问题的答案。
- 计算从城市 s 到城市 t 所需的最短时间。在这里，除了城市 s 和 t 之外，只允许经过城市 1 到 k 。如果城市 t 无法到达或 s = t 无法到达，那么答案应该是 0 。
计算所有三元组 s,t,k 的 f(s,t,k) 并打印它们的总和。更正式地说，输出\displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k) 。
第一行两个数 n,m。
接下来 m 行，每行三个数 u_i,v_i,w_i，表示一条从 u_i 到 v_i，权值为 w_i 的单向边。
最短路径的总和
3 2 1 2 3 2 3 2
25
3 0
0
5 20 1 2 6 1 3 10 1 4 4 1 5 1 2 1 5 2 3 9 2 4 8 2 5 6 3 1 5 3 2 1 3 4 7 3 5 9 4 1 4 4 2 6 4 3 4 4 5 8 5 1 2 5 2 5 5 3 6 5 4 5
517
- 1 \leq N \leq 400
- 0 \leq M \leq N(N-1)
- 1 \leq A_i \leq N (1 \leq i \leq M)
- 1 \leq B_i \leq N (1 \leq i \leq M)
- A_i \neq B_i (1 \leq i \leq M)
- 1 \leq C_i \leq 10^6 (1 \leq i \leq M)
- A_i \neq A_j 或 B_i \neq B_j ，如果是 i \neq j 。
- 输入值均为整数。
样例说明：
s,t,k 这样的三元组 f(s,t,k) \neq 0 如下。
- 对于 k = 1 ： f(1,2,1) = 3, f(2,3,1) = 2 .
- 对于 k = 2 ： f(1,2,2) = 3, f(2,3,2) = 2, f(1,3,2) = 5 .
- 对于 k = 3 ： f(1,2,3) = 3, f(2,3,3) = 2, f(1,3,3) = 5 .