//#include <fstream>
//#include <vector>
//#include <queue>
//#include <limits>
//#include <iostream>
//
//using namespace std;
//int maxim=0;
//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);
//    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){
//            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){
//        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){
//            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){
//        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;maxim+=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>1&&coada>=1){
//        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]<<" ";
//    }
//}
//
//
//
//
//
//
//
//
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
#include <iostream>

using namespace std;
int maxim=0;
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);
    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){
            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){
        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){
            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){
        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;maxim+=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;
    int coada=1;
    while(h>1&&coada>=1){
        int x=min();
        if(v[x]==maxim) break;
        del();coada--;
        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);
                coada++;
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(v[i]==maxim) out<<"0 ";
        else out<<v[i]<<" ";
    }
}