задача 1335

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n, m = list(map(int, input().split()))
inf = 9999999999
a=[[inf]*(n+1) for i in range(n+1)]
for i in range(m):
t=list(map(int, input().split()))
a[t[0]][t[1]]=t[2]
a[t[1]][t[0]]=t[2]
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if a[i][k]+a[k][j]<a[i][j]:
a[i][j]=a[i][k]+a[k][j]
mx=[0]*(n+1)
for i in range(1, n+1):
for j in range(1, n+1):
if a[i][j]>mx[i]:
mx[i]=a[i][j]
res=inf
j=1
for i in range(1, n+1):
if mx[i]<res:
res=mx[i]
j=i
print(j)