#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,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,&m);
    for (i=1;i<=m;++i){
        for (T=3;T;--T)
            gets(ch);
        //scanf("%d %d %d",&a[i],&b[i],&c[i]);
        /*v[a[i]]=new int;
        v[a[i]][g[a[i]]]=b[i];
        cost[a[i]]=new int;
        cost[a[i]][g[a[i]]]=c[i];*/
        //g[a[i]]++;
    }
    
    //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;
}