import strutils,algorithm, sequtils

let get = iterator: string{.closure.}=
  for s in stdin.readLine.split:yield s

proc read:int = get().parseInt
const inf = high(int) div 4




var 
  n,m = read()
  a = newseq[int](m)
  b = newseq[int](m)
  c = newseq[int](m)
  table = newseqwith(n,newseqwith(n,inf))
  next = newseqwith(n,newseq[int](n))

for i in 0..<m:
  var ta,tb,tc = read()
  table[ta-1][tb-1] = tc
  table[tb-1][ta-1] = tc
  
  a[i] = ta
  b[i] = tb
  c[i] = tc


for i in 0..<n:
  for j in 0..<n:
    next[i][j] = j


proc printPath(start,goal:int):seq[int]=
  var cur = start
  result.safeadd(start)
  while cur != goal:
    cur = next[cur][goal]
    result.add(cur)

proc solve():int=
  for k in 0..<n:
    for i in 0..<n:
      for j in 0..<n:
        if table[i][j] > table[i][k]+table[k][j]:
          table[i][j] = table[i][k] + table[k][j]
          next[i][j] = next[i][k]

  return



  

echo solve()