///alg dijkstra---liste
#include<iostream>
#include<fstream>
using namespace std;
const int oo=50002;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct nod{int inf,cost;
nod *urm;};
int d[oo],t[oo],v,n,m,k,s[oo];
nod *l[oo];
void citire(){in>>n>>m;
v=1;
int i,x,y,c;
nod *p;
for(i=1;i<=m;i++){in>>x>>y>>c;
p=new nod;p->inf=y;p->cost=c;p->urm=l[x];l[x]=p;
}
in.close();
}

void rez(){int k,minn,pozmin,i,j,dist;
for(j=1;j<=n;j++)
d[j]=oo;

s[v]=0;d[v]=0;

nod*p;
p=l[v];
while(p){i=p->inf;d[i]=p->cost;t[i]=v;p=p->urm;}

int minn1,minn2,pozmin1,pozmin2;
k=1;
while(k<=n-1){
minn1=minn2=oo;
pozmin1=pozmin2=-1;
for(i=1;i<=n;i++)
if(d[i]<minn1 && s[i]==0){
        minn2=minn1;pozmin2=pozmin1;
        minn1=d[i];pozmin1=i;}
else if(d[i]<minn2&&s[i]==0){minn2=d[i];pozmin2=i;}
pozmin=pozmin1;
minn=minn1;
s[pozmin]=1;

p=l[pozmin];
while(p){if(d[p->inf]>d[pozmin]+p->cost)
    {d[p->inf]=d[pozmin]+p->cost;
    if(p->inf==pozmin2)minn2=d[p->inf];}  p=p->urm;}

k++;
if(k<n-1){
pozmin=pozmin2;
minn=minn2;
s[pozmin]=1;

p=l[pozmin];
while(p){if(d[p->inf]>d[pozmin]+p->cost)
    {d[p->inf]=d[pozmin]+p->cost;}  p=p->urm;}
++k;}
}}

void afisare(){int i;
for(i=1;i<=n;i++)
if(i!=v ){
    if(d[i]==oo)out<<0<<" ";
else
    out<<d[i]<<" ";}}


int main(){
citire();
rez();
afisare();
return 0;}