#include <fstream>
#include <vector>
#include <queue>
#include <limits>
#include <iostream>

using namespace std;
const int maxim=numeric_limits<int>::max()/2;
int n;
vector<pair<int,int> > nod[50001];
int v[50001];
int h;
int heap[50001];
int pos[50001];



int parent(int n){
    return n/2;
}
int first(int n){
    return 2*n;
}
int second(int n){
    return 2*n+1;
}

bool comp(int f,int s){
    return v[heap[f]]<v[heap[s]];
}
void swap(int f,int s){
    std::swap(heap[f],heap[s]);
    pos[heap[f]]=f;
    pos[heap[s]]=s;
}


int min(){
    return heap[1];
}
void del(){
    int n=1;
    swap(n,h+1-1);
    h--;
    while(parent(n)&&comp(n,parent(n))){swap(n,parent(n));n=parent(n);}
    bool go=true;
    while(go){
        go=false;
        if(second(n)<h+1){
            if(comp(second(n),n)){
                if(comp(first(n),second(n))){
                    swap(first(n),n);go=true;n=first(n);
                }else{
                    swap(second(n),n);go=true;n=second(n);
                }
            }else if(comp(first(n),n)){
                swap(first(n),n);go=true;n=first(n);
            }
        }
    }
    if(first(n)<h+1){
        if(comp(first(n),n)){
            swap(first(n),n);go=true;n=first(n);
        }
    }
}
void refa(int k){
    int n=pos[k];
    while(parent(n)&&comp(n,parent(n))){swap(n,parent(n));n=parent(n);}
    bool go=true;
    while(go){
        go=false;
        if(second(n)<h+1){
            if(comp(second(n),n)){
                if(comp(first(n),second(n))){
                    swap(first(n),n);go=true;n=first(n);
                }else{
                    swap(second(n),n);go=true;n=second(n);
                }
            }else if(comp(first(n),n)){
                swap(first(n),n);go=true;n=first(n);
            }
        }
    }
    if(first(n)<h+1){
        if(comp(first(n),n)){
            swap(first(n),n);go=true;n=first(n);
        }
    }
}


int main(){
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int m;in>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,c;
        in>>x>>y>>c;
        nod[x].push_back(make_pair(y,c));
        nod[y].push_back(make_pair(x,c));
    }
    for(int i=0;i<50001;i++){
        v[i]=maxim;
        heap[i]=i;
        pos[i]=i;
    }
    h=n;
    v[1]=0;
    while(h>0){
        int x=min();
        if(v[x]==maxim) break;
        del();
        for(int i=0;i<nod[x].size();i++){
            int t=nod[x][i].first;int c=nod[x][i].second;
            if(v[t]>v[x]+c){
                v[t]=v[x]+c;
                refa(t);
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(v[i]==maxim) out<<"0 ";
        else out<<v[i]<<" ";
    }
}