f=open("input.txt")
d=f.readline().split()
n=int(d[0])
m=[[1000000]*n for i in range(n)]
for i in range(int(d[1])):
  d=map(int, f.readline().split())
  m[d[0]-1][d[1]-1]=d[2]
  m[d[1]-1][d[0]-1]=d[2]
for rida in m:
  print rida
i=1
g={}
g[0]=0
g[1]=m[0][1]
g[2]=min(g[1]+m[1][2], m[0][2])
g[3]=min(g[2]+m[3][2], g[1]+m[1][2])
print g
exit()

######

while i<n:
 g[1<<i]=m[0][i] 
 i=i+1
i=1
while i<n:
 j=i+1
 while j<n:
   v1=g[1<<i]+m[i][j]
   v2=m[0][j]
   if v1<v2: g[1<<i|1<<j]=v1
   else: g[1<<i|1<<j]=v2  
   print j
   j+=1
 i+=1
print g
for k in g.keys():
  print "{0:06b}".format(k)+" "+str(g[k])