この問題はワーシャル-フロイド法というアルゴリズムのアイディア部分を抽出して問題にしたものになっています。

便宜上 \(f(s,t,0)\) を次のように定めます。

\[ f(s,t,0) = \begin{cases} 0 & s = t \\ 辺s\to tの重み & 辺が存在する \\ \mathrm{inf} & 辺が存在しない \end{cases} \]

\(f(s,t,k+1)\) を \(f(\ast,\ast,k)\) を用いて表すことを考えます。頂点 \(s,t\) および \(k+1\) 以下の番号の頂点を使ってよいときの \(s \to t\) 間の最短パスは \(k+1\) を使うかどうかで2つに場合分け出来ます。それぞれの場合について最短パスは以下のように計算できます。

• \(k+1\) を使わない場合
  • 使用してよいのは \(s,t\) および \(k\) 以下の番号の頂点であり、この時の最短パスの長さは \(f(s,t,k)\) が答えです。
• \(k+1\) を使う場合
  • \(s\) から \(k+1\) への \(k\) 以下の頂点を経由する最短パス、および \(k+1\) から \(t\) への \(k\) 以下の頂点を経由する最短パスがわかればよいです。これは \(f(s,k+1,k) + f(k+1,t,k)\) になります。

以上より \(f(s,t,k+1)\) と \(f(\ast,\ast,k)\) の関係式は次の通りです。

\[f(s,t,k+1) = \min(f(s,t,k) , f(s,k+1,k) + f(k+1,t,k))\]

以上の遷移式を元にDPを行うことで \(\mathrm{O}(N^3)\) でこの問題を解くことが出来ました。

なお、 \(f(s, t, N)\) は全ての頂点を通過できるときの \(s\) から \(t\) へ向かう最短パスになっています。このように全ての \((s,t)\) に対して \(\mathrm{O}(N^3)\) で \(s\) から \(t\) へ向かう最短パスを計算するアルゴリズムをワーシャル-フロイド法と呼びます。

以下に Python での実装例を貼ります。( 以下のコードは Python3 だと TLE してしまうので、 Python で AC を目指す場合はより高速な処理系である PyPy3 を言語欄から選んで提出するとよいでしょう。)

import sys

N, M = map(int, sys.stdin.buffer.readline().split())
ABC = map(int, sys.stdin.buffer.read().split())
d = [[1 << 60] * N for i in range(N)]
for i in range(N):
  d[i][i] = 0
for a, b, c in zip(ABC, ABC, ABC):
  d[a - 1][b - 1] = c
answer = 0
for k in range(N):
  nxt = [[0] * N for i in range(N)]
  for i in range(N):
    for j in range(N):
      nxt[i][j] = min(d[i][j], d[i][k] + d[k][j])
      if nxt[i][j] < 1 << 59:
        answer += nxt[i][j]
  d = nxt
print(answer)