program dijkstra1;
var x:array[1..50000,1..50000] of longint;
    n,m:longint;
procedure citire;
var a,b,i,j,k,c:longint;
    f:text;
begin
assign(f,'dijkstra.in');
reset(f);
readln(f,n,m);
for i:=1 to n do
for j:=1 to n do
x[i,j]:=0;
for k:=1 to m do
begin
readln(f,a,b,c);
x[a,b]:=c;
end;
close(f);
for i:=1 to n do
for j:=1 to n do
if (i<>j) and (x[i,j]=0) then
x[i,j]:=100000;
end;
procedure generare;
var i,j,k:longint;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if x[i,j]>x[i,k]+x[k,j] then
x[i,j]:=x[i,k]+x[k,j];
end;
procedure afisare;
var j:longint;
    f:text;
begin
assign(f,'dijkstra.out'); rewrite(f);
for j:=2 to n do
if x[1,j]=100000 then
write(f,'0')
else
write(f,x[1,j],' ');
close(f);
end;
begin
citire;
generare;
afisare;
end.