#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

typedef struct{int nod; int ct;} pct;

bool operator<(pct x, pct y){
    return x.ct>y.ct;
}

const int maxx=1<<30;

priority_queue< pct > q;
vector< int > a[50001];
vector< int > c[50001];
int n,m,v[50001],cost[50001];


void citire(){
    int i,x,y,z;
    freopen("dijkstra.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(i=0;i<m;++i){
        scanf("%d %d %d",&x,&y,&z);
        a[x].push_back(y);
        c[x].push_back(z);
    }
}


void dijkstra(){
    pct t,t1;
    int x,y,i;
    for(i=1;i<=n;++i)
    cost[i]=maxx;
    t.nod=1;
    t.ct=0;
    cost[1]=0;
    q.push(t);
    while(!q.empty()){
        t=q.top();
        q.pop();
        if(!v[t.nod]){
        x=t.nod;
        v[x]=1; //printf("%d are %d vecini\n",x,a[x].size());
        for(i=0;i<a[x].size();++i)
            if(t.ct+c[x][i]<cost[a[x][i]])
                {cost[a[x][i]]=t.ct+c[x][i]; //printf("add %d\n",a[x][i]);
                t1.nod=a[x][i]; t1.ct=cost[t1.nod];
                q.push(t1);
                }
        }
    }
}


int main(){
    citire();
    dijkstra();
 /*  int i,j;
    for(i=1;i<=n;++i){
        for(j=0;j<a[i].size();++j)
        printf("(%d %d) ",a[i][j],c[i][j]);
    printf("\n");
   } */
   for(int i=1;i<=n;++i)
    if(cost[i]==maxx) cost[i]=0;
    freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=n;++i)
    printf("%d ",cost[i]);
}