Флойд

inf = float('inf')
n, m = map(int, input().split())
mx = [[inf for i in range(m)] for j in range(n)]
for i in range(m):
    x, y, w = map(int, input().split())
    mx[x][y] = w
    mx[y][x] = w
for k in range(n):
    for x in range(n):
        for y in range(n):
            if mx[x][y] < mx[x][k] + mx[k][y]:
                mx[x][y] = mx[x][k] + mx[k][y]