# задача 1334

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40``` ```n, m = map(int, input().split()) graph = [[1000000000000 for i in range(n)] for j in range(n)] for i in range(m): a, b, c = map(int, input().split()) graph[a-1][b-1] = c graph[b-1][a-1] = c for k in range(n): for i in range(n): for j in range(n): if graph[i][k] + graph[k][j] < graph[i][j]: graph[i][j] = graph[i][k] + graph[k][j] for i in range(n): for j in range(n): if graph[i][j] == 1000000000000: graph[i][j] = -1 if i == j: graph[i][i] = 0 print(max([max(i) for i in graph])) ''' n, m = [int(s) for s in input().split()] min_dist = [[float('+inf')]*n for i in range(n)] for i in range(m): a = [int(s) for s in input().split()] min_dist[a[0]-1][a[1]-1] = a[2] min_dist[a[1]-1][a[0]-1] = a[2] for k in range(n): for i in range(n): for j in range(n): if i == j: min_dist[i][j] = 0 else: min_dist[i][j] = min(min_dist[i][j], min_dist[i][k]+min_dist[k][j]) c = 0 for i in range(n): for elem in min_dist[i]: if elem > c and elem!=float('+inf'): c = elem print(c) ''' ```