# INF float inf int input list map int input split for in range for in r

 ``` 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 41``` ```INF = float('inf') N = int(input()) W = [list(map(int, input().split())) for i in range(N)] for i in range(N): for j in range(N): if W[i][j] == 0:W[i][j] = INF for g in range(N-1): n = g + 1 active = [True] * N R = W[n - 1][:] P = [n - 1] * N active[n - 1] = False P[n - 1] = -1 kMin = -1 for i in range(N - 1): minDist = INF for j in range(N): if active[j] and R[j] < minDist: minDist = R[j] kMin = j if kMin != -1: active[kMin] = False for j in range(N): if R[kMin] + W[kMin][j] < R[j]: R[j] = R[kMin] + W[kMin][j] P[j] = kMin for i in range(g+1,N): m = i + 1 print('(' + str(n) + ',' + str(m) + '):', end=" ") if R[m - 1] != INF: i = m - 1 a = [] while i != n - 1: i = P[i] a = [i + 1] + a a = a + [m] for i in range(len(a)): print(a[i], end=" ") print('(' + str(R[m - 1]) + ')') else: print(0) ```