ワーシャル・フロイド法

E - 全点対最短経路問題

O(N³)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    INF = 10**18
    N, M = list(map(int, input().split()))
    dist = []
    for i in range(N):
        dist.append([])
        for j in range(N):
            dist[i].append(INF)

    for _ in range(M):
        u, v, c = list(map(int, input().split()))
        dist[u][v] = c

    for i in range(N):
        dist[i][i] = 0

    for k in range(N):
        for x in range(N):
            for y in range(N):
                dist[x][y] = min(dist[x][y], dist[x][k] + dist[k][y])

    ans = 0
    for i in range(N):
        for j in range(N):
            ans += dist[i][j]

    print(ans)    

# エントリポイント
if __name__ == '__main__':
    main()