{Se da un graf orientat prin matricea costurilor si un nod x.
Sa se determine dr de lungime minimade la x la toate vf din graf
precum si costurile acestor drumuri}

{Met Greedy: se selecteaza vf grafului in n-1 pasi in ordine cresc
a costului dr de la x la ele, intr-o mult care init contine vf de start

pred[i]=k daca k e predecesorul lui ipe dr minim de la x la i
d[i]=costul minim de la x la i
s[i]=1 daca vf i este selectat
}

const pinfinit=Maxint;
type mat=array[1..50000,1..50000] of integer;
     vect=array[1..50000] of integer;
var c:mat;
    s,prec:vect;
    d:array[1..50000] of longint;
    vf,min,x,i,j,k,cost:integer; g:boolean;
    n,m:longint;
    f,q:text;

procedure tipar(vf:integer);
begin
if prec[vf]<>0 then
        begin
          tipar(prec[vf]);
          write(vf:4);
        end
           else write(vf:4);
end;

procedure citire;
var    m,x,y,z:integer;
begin
        assign(f,'dijkstra.in'); reset(f);
        readln(f,n,m);
        for i:=1 to n do
                for j:=1 to n do
                        if i=j then c[i,j]:=0 else c[i,j]:=pinfinit;
        for i:=1 to m do begin
                readln(f,x,y,z);
                c[x,y]:=z;
                end;
        close(f);
end;


begin{program principal}

citire;
assign(q,'dijkstra.out'); rewrite(q);
x:=1;
for i:=1 to n do
   begin
     s[i]:=0;
     d[i]:=c[x,i];
     if d[i]<pinfinit then prec[i]:=x
                     else prec[i]:=0;
   end;
s[x]:=1;
d[x]:=0;
prec[x]:=0;

repeat
   g:=false;
   min:=pinfinit;
   for j:=1 to n do
    if (s[j]=0)and(d[j]<min) then
    begin
      g:=true;min:=d[j];k:=j;
    end;
   s[k]:=1;
   for i:=1 to n do
       if s[i]=0 then
         if d[i]>d[k]+c[k,i] then
              begin
                 d[i]:=d[k]+c[k,i];
                 prec[i]:=k;
              end;
until not(g);

for i:=1 to n do
 if i<>x then
   if d[i]=pinfinit then write(g,'0 ')
                    else
   begin
      write(g,d[i],' ');
   end;
 close(q);

end.