#made in 2019/7/1
#modified in 2020/2/14
class Node:
    def __init__(self):
        self.next={}
    def get_data(self,new_next,weight=1):
        self.next[new_next]=weight



def dijkstra():
    total=0
    node_cost=[float("inf") for i in range(0,N)]
    now=[E-1]
    node_cost[now[0]]=0
    check=[i for i in range(0,N)]
    check.remove(E-1)
    next_node=node[now[0]].next.keys()
    while len(check):
        total+=1
        tmp=[]
        #print("now", now)
        for each in now:
            next_node=node[each].next.keys()
            for i in next_node:
                val=node[each].next[i]+node_cost[each]
                if node_cost[i]>val:
                    node_cost[i]=val
                    if i in check:
                        #check.remove(i)
                        #tmp.extend(node[i].next.keys())
                        tmp.append(i)
        now=tmp
        #print("next... ",tmp)
        #print("now...",node_cost)
        if len(now)==0:
            break
        
    print(node_cost)
    print("min_cost:",node_cost[S-1])
    



def BFS():
    total=0
    #print("start bfs")
    check_node=[i for i in range(0,N)]
    now=S-1
    tmp=[now]
    check_node.remove(now)
    new_tmp=[]
    while len(check_node)>0:
        #print("tmp:{}".format(tmp))
        total+=1
        for each in tmp:
            #print("each:{}".format(each))
            for i in node[each].next.keys():
                k=i
                #print(k)
                if k in check_node:
                    #print("append :{}".format(k))
                    new_tmp.append(k)
                    check_node.remove(k)
        #print("new_tmp:{}".format(new_tmp))
        #print("check_node:{}".format(check_node))
        tmp=new_tmp
        new_tmp=[]
    print("end")
    print("loop time:{}".format(total))
    







        
        


#??
N,M=list(map(int,input().split()))
#S,E=list(map(int,input().split()))
node=[Node() for _ in range(N)]
ans=[[100 for _ in range(N)]for _ in range(N)]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    node[tmp_p-1].get_data(tmp_n-1,tmp_w)
    node[tmp_n-1].get_data(tmp_p-1,tmp_w)
#BFS()
a_num=ord("a")
for i in range(N):
    #print(chr(a_num+i),"→",chr(a_num+j))
    S=i+1
    E=i+1
    dijkstra()
    print()

