#include<fstream>
#include<vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int INF = 0x3f3f3f3f;
const int Nmax = 50001;
vector<int> G[Nmax],C[Nmax];
struct hi{int x,cost;hi(){}hi(int _x,int _c){x=_x,cost=_c;}};
class he{
    private:
    hi A[Nmax];
    int pos[Nmax],K;
    void upheap(int i){
        if(i>=1 && A[i].cost < A[i/2].cost){
            swap(pos[A[i].x],pos[A[i/2].x]);
            swap(A[i],A[i/2]);
            upheap(i/2);
        }
    }
    void downheap(int i){
        if(2*i+1<=K && A[2*i+1].cost <= A[2*i].cost && A[2*i+1].cost < A[i].cost){
            swap(pos[A[2*i+1].x],pos[A[i].x]);
            swap(A[2*i+1],A[i]);
            downheap(2*i+1);
        }
        else if(2*i<=K && A[2*i].cost < A[i].cost){
            swap(pos[A[2*i].x],pos[A[i].x]);
            swap(A[2*i],A[i]);
            downheap(2*i);
        }
    }
    public:
    void push(int node,int cost){
        if(pos[node]){
            if(cost < A[pos[node]].cost){
                A[pos[node]].cost=cost;
                upheap(pos[node]);
            }
        }
        else{
            A[++K]=hi(node,cost);
            pos[node]=K;
            upheap(K);
        }
    }
    void pop(){
        pos[A[1].x]=0;
        pos[A[K].x]=1;
        swap(A[1],A[K]),K--;
        downheap(1);
    }
    hi top(){
        return A[1];
    }
    int size(){
        return K;
    }
} H;
int N,M,D[Nmax];
int main(){
    in>>N>>M;
    int x,y,c;
    for(int i=1;i<=M;i++){
        in>>x>>y>>c;
        G[x].push_back(y);
        C[x].push_back(c);
    }
    for(int i=1;i<=N;i++) D[i]=INF;
    D[1]=0; H.push(1,0);
    while(H.size()){
        hi p=H.top(); H.pop();
        for(int i=0;i<G[p.x].size();i++){
            if( p.cost + C[p.x][i] < D[G[p.x][i]] ){
                D[G[p.x][i]] = p.cost + C[p.x][i];
                H.push(G[p.x][i],D[G[p.x][i]]);
            }
        }
    }
    for(int i=2;i<=N;i++) out<<(D[i]==INF?0:D[i])<<' ';
    return 0;
}