#include <stdio.h>
#include <stdlib.h>   
//#include <bitset>
#include <queue>
//#include <algorithm>
#define nMax 50005
#define INF 2147000000
using namespace std;
int n,m,i,j,nod,T,x,y,z;
int g[nMax],d[nMax];
int a[250005],b[250005],c[250005];
char ch[32];
bool iq[nMax];
queue <int> Q;
int *v[nMax],*cost[nMax];

void read(){
    scanf("%ld %ld\n",&n,&m);
    for (i=1;i<=m;++i){
        gets(ch);
        x=y=z=j=0;
        while (ch[j]!=' '){x=x*10+ch[j]-'0';j++;}j++;
        while (ch[j]!=' '){y=y*10+ch[j]-'0';j++;}j++;
        while (ch[j]){z=z*10+ch[j]-'0';j++;}
        g[x]++;a[i]=x;b[i]=y;c[i]=z;
    }
    for (i=1;i<=n;++i) v[i]=(int*) malloc (g[i]*sizeof(int));
    for (i=1;i<=n;++i){ cost[i]=(int*) malloc (g[i]*sizeof(int)); 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];
        g[a[i]]++;
    }
}

int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    read();
    //////////////////
    
    for (i=2;i<=n;++i)d[i]=INF;d[1]=0;
    while(!Q.empty())Q.pop();
    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;
}