问题描述

在高桥王国中有 $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)$。

约束条件

• $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)$
• 如果 $i \\neq j$，则 $A_i \\neq A_j$ 或者 $B_i \\neq B_j$。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $A_1$ $B_1$ $C_1$ $\\vdots$ $A_M$ $B_M$ $C_M$

输出

输出 $\\displaystyle \\sum_{s = 1}^N \\sum_{t = 1}^N \\sum_{k = 1}^N f(s, t, k)$。

示例输入 1

3 2
1 2 3
2 3 2

示例输出 1

25

对于 $f(s,t,k) \\neq 0$ 的三元组 $s,t,k$ 如下所示。

• 对于 $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$。

示例输入 2

3 0

示例输出 2

0

对于所有 $s,t,k$，我们有 $f(s,t,k) = 0$。

示例输入 3

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

示例输出 3

517