D - 最短路径查询 2

给定Takahashi王国中的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。

计算$f(s,t,k)$的所有三元组$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)$
• $A_i \neq A_j$或$B_i \neq B_j$，如果$i \neq j$。
• 输入中的所有值都为整数。

输入

从标准输入读入数据，数据格式如下：

$N$ $M$

$A_1$ $B_1$ $C_1$

...

$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