#include<cstdio>
const int N=50001,I=1<<30;
struct G
{
int o,c;
G *n;
};
int n,m,i,x,y,z,d[N],h[N],p[N],k,l;
G *a[N],*q;
void swap(int x, int y)
{
int t = h[x];
h[x] = h[y];
h[y] = t;
}
void upheap(int what)
{
int tata;
while(what>1)
{
tata=what>>1;
if(d[h[tata]]>d[h[what]])
p[h[what]]=tata,p[h[tata]]=what,swap(tata,what),what=tata;
else
what=1;
}
}
void downheap(int what)
{
int f;
while(what<=k)
{
f=what;
if((what<<1)<=k)
{
f=what<<1;
if(f+1<=k)
if(d[h[f+1]]<d[h[f]])
++f;
}
else
return;
if(d[h[what]]>d[h[f]])
p[h[what]]=f,p[h[f]]=what,swap(what,f),what=f;
else
return;
}
}
int main()
{
freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
while(m--)
scanf("%d%d%d",&x,&y,&z),q=new G,q->o=y,q->c=z,q->n=a[x],a[x]=q;
for(i=2;i<=n;i++)
d[i]=I,p[i]=-1;
for(p[1]=h[++k]=1;k;)
for(l=h[1],swap(1,k),p[h[1]]=1,k--,downheap(1),q=a[l];q;q=q->n)
if(d[q->o]>d[l]+q->c)
{
d[q->o]=d[l]+q->c;
if(p[q->o]!=-1)
upheap(p[q->o]);
else
h[++k]=q->o,p[h[k]]=k,upheap(k);
}
for(i=2;i<=n;i++)
printf("%d ",d[i]==I?0:d[i]);
}