#include<stdio.h>
#define Nmax 50005
#define inf 1000000000
int a[5*Nmax],n,m,b[5*Nmax],c[5*Nmax],d[Nmax],i,j,k,l,ok;

int main(){

freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);

scanf("%d %d",&n,&m);

for(i=1;i<=m;i++)
        {scanf("%d %d %d",&a[i],&b[i],&c[i]);
        if(a[i]==1)
                d[b[i]]=c[i];
        }

for(i=2;i<=n;i++)
        if(d[i]==0)
                d[i]=inf;

ok=0;

while(!ok){
ok=1;
for(i=1;i<=m;i++)
        if(d[b[i]]>(d[a[i]]+c[i]))
                {d[b[i]]=d[a[i]]+c[i];ok=0;}

       }

for(i=2;i<=n;i++)
if(d[i]!=inf)
        printf("%d ",d[i]);
else
        printf("%d ",0);

                
return 0;}
}