#include<stdio.h>
#define Nmax 50001
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]=1000000000;

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]!=1000000000)
        printf("%d ",d[i]);
else
        printf("%d ",-1);

                
return 0;}