#include<fstream>
#include<vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int INF = 0x3f3f3f3f;
const int Nmax = 50001,Mmax = 250001;
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+Mmax];
    int K;
    void upheap(int i){
        if(i>=1 && A[i].cost < A[i/2].cost){
            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(A[2*i+1],A[i]);
            downheap(2*i+1);
        }
        else if(2*i<=K && A[2*i].cost < A[i].cost){
            swap(A[2*i],A[i]);
            downheap(2*i);
        }
    }
    public:
    void push(int node,int cost){
        A[++K]=hi(node,cost);
        upheap(K);
    }
    void pop(){
        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();
        if(p.cost > D[p.x]) continue;
        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;
}