#include<fstream>
#include<vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int MAXN = 50001;
const int MAXM = 50001;
const int INF = 1 << 30;
struct item{
    int val,node;
};
item A[MAXN+MAXM+69];
int k;
void swap(int a,int b){
    item X=A[a];
    A[a]=A[b];
    A[b]=X;
}
item mp(int a,int b){
    item u;
    u.val=a;
    u.node=b;
    return u;
}
void upheap(int i){
    if(A[i/2].val>A[i].val){
        swap(i/2,i);
        upheap(i/2);
    }
}
void downheap(int i){
    if( 2*i+1<=k && A[2*i+1].val<A[i].val){
        swap(2*i+1,i);
        downheap(2*i+1);
    }
    else if( 2*i<=k && A[2*i].val<A[i].val){
        swap(2*i,i);
        downheap(2*i);
    }
}
item First(){
    item X=A[1];
    swap(1,k);
    --k;
    downheap(1);
    return X;
}
void Insert(item x){
    A[++k]=x;
    upheap(k);
}
vector<int> G[MAXN],C[MAXN];
int D[MAXN];
int N,M;
int a,b,c;
item u;
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        in>>a>>b>>c;
        G[a].push_back(b);
        C[a].push_back(c);
    }
    for(int i=2;i<=N;i++) D[i]=INF;
    Insert(mp(0,1));
    while(k>0){
        u=First();
        if(u.val == D[u.node])
        for(int i=0;i<G[u.node].size();i++){
            if( D[G[u.node][i]] > u.val+C[u.node][i] ){
                D[G[u.node][i]] = u.val+C[u.node][i];
                Insert(mp(D[G[u.node][i]],G[u.node][i]));
            }
        }
    }
    for(int i=2;i<=N;i++) out<<(D[i]==INF?0:D[i])<<' ';
    return 0;
}