题目描述

高橋王国には $N$ 個の都市と $M$ 本の道路があります。

都市には $1$ から $N$ の番号が、道路には $1$ から $M$ の番号が割り振られています。道路 $i$ は都市 $A_i$ から $B_i$ へ向かう一方通行の道で、移動するのに $C_i$ 分かかります。

$f(s,\ t,\ k)$ を次のクエリへの答えとして定めます。

• 都市 $s$ を出発して都市 $t$ に到着するまでの最短時間を計算してください。ただし、通ってよい都市は $s,\ t$ および番号が $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) $ を出力せよ。

题目大意

题目描述

给出一张 $n$ 个点，$m$ 条边的的有向图。设 $f(s,t,k)$ 表示从点 $s$ 到点 $t$，只经过点 $1$ 到 $k$ 以及 $s,t$ 的最短路径，如果不存在则为 $0$。

你需要求出以下式子的值：

输入格式

第一行两个数 $n,m$。

接下来 $m$ 行，每行三个数 $u_i,v_i,w_i$，表示一条从 $u_i$ 到 $v_i$，权值为 $w_i$ 的单向边。

Translated by _Ponder_

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)$
• $i\ \neq\ j$ ならば $A_i\ \neq\ A_j$ または $B_i\ \neq\ B_j$ である。
• 入力は全て整数である。

Sample Explanation 1

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

Sample Explanation 2

全ての $s,t,k$ に対して $f(s,t,k)\ =\ 0$ です。