Contest Duration: - (local time) (100 minutes) Back to Home
D - Shortest Path Queries 2 /

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

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

• 都市 s を出発して都市 t に到着するまでの最短時間を計算してください。ただし、通ってよい都市は s, t および番号が k 以下の都市のみとします。また、都市 t に到着できない場合や s = t である場合におけるクエリの答えは 0 とします。

制約

• 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


入力例 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


Score : 400 points

Problem Statement

There are N cities and M roads in the Kingdom of Takahashi.

The cities are numbered 1 through N, and the roads are numbered 1 through M. Road i is a one-way road that leads from City A_i to City B_i, and it takes C_i minutes to go through it.

Let us define f(s, t, k) as the answer to the following query.

• Compute the minimum time needed to get from City s to City t. Here, other than the Cities s and t, it is only allowed to pass through Cities 1 through k. If City t is unreachable or s = t, the answer should be 0.

Compute f(s,t,k) for all triples s,t,k and print the sum of them. More formally, print \displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k).

Constraints

• 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 or B_i \neq B_j, if i \neq j.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M


Output

Print \displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k).

Sample Input 1

3 2
1 2 3
2 3 2


Sample Output 1

25


The triples s,t,k such that f(s,t,k) \neq 0 are as follows.

• For k = 1: f(1,2,1) = 3, f(2,3,1) = 2.
• For k = 2: f(1,2,2) = 3, f(2,3,2) = 2, f(1,3,2) = 5.
• For k = 3: f(1,2,3) = 3, f(2,3,3) = 2, f(1,3,3) = 5.

Sample Input 2

3 0


Sample Output 2

0


We have f(s,t,k) = 0 for all s,t,k.

Sample Input 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


Sample Output 3

517