#include <stdio.h>
#include <bitset>
#include <queue>
#include <string.h>
#define nMax 65536
#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)
        printf("%ld ",d[i]);
        
return 0;
}