AT_abc208_d [ABC208D] Shortest Path Queries 2

[problemUrl]: https://atcoder.jp/contests/abc208/tasks/abc208_d 高橋王国には $ 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) $ を出力せよ。

### 制約 - $ 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 $ です。