#include <bits/stdc++.h>
using namespace std;
int N,M,d[50001],A,B,c;
vector <int> G[50001],C[50001];
queue <int> coada;
int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);
    while(M){
        scanf("%d%d%d",&A,&B,&c);
        G[A].push_back(B);
        C[A].push_back(c);
        --M;
    }
    for(int i=2;i<=N;++i)
        d[i]=0x3f3f3f3f;
    coada.push(1);
    while(!coada.empty()){
        int x=coada.front();
        for(int i=0;i<G[x].size();++i)
            if(d[G[x][i]]>d[x]+C[x][i]){
                d[G[x][i]]=d[x]+C[x][i];
                coada.push(G[x][i]);
            }
        coada.pop();
    }
    for(int i=2;i<=N;++i)
        printf("%d ",d[i]==0x3f3f3f3f ? 0 : d[i]);
    return 0;
}