最短路查询 2

题目描述

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

样例

3 2
1 2 3
2 3 2

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$。

3 0

0

对所有的 $s,t,k$ 都有 $f(s,t,k) = 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 \le N \le 400$
• $0 \le M \le N(N-1)$
• $1 \le A_i \le N$ $(1 \le i \le M)$
• $1 \le B_i \le N$ $(1 \le i \le M)$
• $A_i \neq B_i$ $(1 \le i \le M)$
• $1 \le C_i \le 10^6$ $(1 \le i \le M)$
• 当 $i \neq j$ 时，$A_i \neq A_j$ 或 $B_i \neq B_j$
• 输入均为整数