#無向グラフ
class Graph():
    #初期変数は頂点数、辺数、標準入力から受け取った配列形式の入力
    def __init__(self,vertex_num,node_num,naive_input):
        self.vertex_num=vertex_num
        self.node_num=node_num
        #nodeには入力時のインデックスも含む
        #[接続ノード , インッデクス]のarray
        node=[[] for _ in range(vertex_num)]
        for i in range(node_num):
            u,v=naive_input[i][:2]
            w=naive_input[i][2]
            node[u].append([v,i,w])
            node[v].append([u,i,w])
        self.node=node
        #それぞれの頂点の辺の数
        self.node_num_arr=list(map(lambda x:len(x),node))
    #頂点nowから順にbfs
    def bfs(self,s=0):
        #最短経路＋αで問題を解くと思うのでcal_distance内で問題を解くための関数を実行する形の方が自然？
        def cal_distance(now_edge,next_edge_info,distance_arr,before_vertex_arr,queue,l_ind):
            next_edge=next_edge_info[0]
            weight=next_edge_info[2]
            cal_distance_val=distance_arr[now_edge]+weight
            if before_vertex_arr[next_edge]==-1:
                    queue[l_ind]=next_edge
                    #print("queue is updated")
                    l_ind+=1
            if cal_distance_val<distance_arr[next_edge]:
                #配列渡しなのでこのあたりは返り値に持たせる必要無し
                distance_arr[next_edge]=cal_distance_val
                before_vertex_arr[next_edge]=now_edge
                #for debug
                #print(now_edge,"→",next_edge,":",cal_distance_val)
                #print(distance_arr)
                #print(before_vertex)
                
            return l_ind

        #bfs用のキュー
        q=[-1 for _ in range(self.vertex_num)]
        #pypyを使うときは要変更
        #ダイクストラ使用に伴って削除
        #訪問済み頂点は距離から導出
        #cal_node_num_arr=self.node_num_arr.copy()
        now_ind=0
        q[now_ind]=s
        last_ind=1


        distance=[float("inf") for _ in range(self.vertex_num)]
        distance[s]=0
        before_vertex=[-1 for _ in range(self.vertex_num)]
        before_vertex[s]=s
        index_arr=[-1 for _ in range(self.node_num)]

        while last_ind<self.vertex_num:
            now_edge=q[now_ind]
            """
            print()
            print()
            print("now_node:",now_edge)
            print("now_ind:",now_ind,"last_ind",last_ind)
            print(q)
            print(before_vertex)
            """
            for next_edge_info in self.node[now_edge]:
                #インデックスを利用したいときは要修正
                #cal_node_num_arr[now_edge]-=1
                #cal_node_num_arr[next_edge]-=1
                #q[last_ind]=next_edge
                ##ここにやりたい処理をぶち込む！！
                #######cal_hogehoge()

                #頂点sから各頂点までの距離を計算する

                last_ind=cal_distance(now_edge,next_edge_info,distance,before_vertex,q,last_ind)
                
            now_ind+=1
        
        return distance

n,m=list(map(int,input().split()))
"""
maze=[[i for i in input()] for _ in range(n)]
graph=[[] for _ in range(n*m)]
q_num=0
for i in range(n):
    for j in range(m):
        if maze[i][j]=="#":
            continue
        ind=i*m+j
        q_num+=1
        #move[i][j]=ind
        if i!=0:
            if maze[i-1][j]!="#":
                graph[ind].append((i-1)*m+j)
        if i!=n-1:
            if maze[i+1][j]!="#":
                graph[ind].append((i+1)*m+j)
        if j!=0:
            if maze[i][j-1]!="#":
                graph[ind].append(i*m+j-1)
 
        if j!=m-1:
            if maze[i][j+1]!="#":
                graph[ind].append(i*m+j+1)

a=[]
for num,i in enumerate(graph):
    for j in i:
        a.append([num,j,1])
#print(a)
tmp=0
for i in maze:
    for j in i:
        if j==".":
            tmp+=1
n=tmp
m=len(a)
"""
a=[list(map(int,input().split())) for _ in range(m)]
a=list(map(lambda x:[x[0]-1,x[1]-1,x[2]],a))
G=Graph(n,m,a)
ans=0
for i in range(n):
    cal=G.bfs(i)