#include <stdio.h>   
#include <bitset>   
#include <queue>   
#include <string.h>   
#define nMax 50002   
#define INF 0x3f3f3f3f   
using namespace std;   
long n,m,i,j,nod;   
long a[nMax],b[nMax],c[nMax],g[nMax],*v[nMax],*cost[nMax];   
long d[nMax];   
bitset <nMax> iq;   
  
int main(){   
    freopen("dijkstra.in","r",stdin);   
    freopen("dijkstra.out","w",stdout);   
    scanf("%ld %ld\n",&n,&m);   
    for (i=1;i<=m;++i){   
        scanf("%ld %ld %ld\n",&a[i],&b[i],&c[i]);   
       g[a[i]]++;    
    }   
    for (i=1;i<=n;++i){   
        v[i]=(long*)malloc((g[i]+1)*sizeof(long));   
        cost[i]=(long*)malloc((g[i]+1)*sizeof(long));   
        g[i]=0;   
    }   
    for (i=1;i<=m;++i){   
        v[a[i]][g[a[i]]]=b[i];   
        cost[a[i]][g[a[i]]++]=c[i];   
    }   
    ///////////////////   
    memset(d,INF,sizeof(d));d[1]=0;   
    queue <long> Q;   
    Q.push(1);iq[1]=1;   
    while (!Q.empty()){   
          nod=Q.front(); Q.pop();   
          iq[nod]=0;   
          for (i=0;i<g[nod];++i)   
              if (d[nod]+cost[nod][i] < d[v[nod][i]]){   
                 d[v[nod][i]]=d[nod]+cost[nod][i];   
                 if (!iq[v[nod][i]]){   
                    Q.push(v[nod][i]);   
                    iq[v[nod][i]]=1;   
                 }   
              }   
    }   
    //////////////////////////   
    for (i=2;i<=n;++i)   
        if (d[i]!=INF)printf("%ld ",d[i]);
        else printf("0 ");   
           
return 0;   
}