#include<fstream>
#include<vector>
#include<set>
#define INF 1000000000
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");


int main(){

    set < pair < int , int > > H;
    int n, m, path[50004];
    vector < pair < int , int > > nod[50004];



    cin>>n>>m;

    while(m--){
        int x, y, z;
        cin>>x>>y>>z;
        nod[x].push_back(make_pair(y,z));
    }

    for(int i = 2; i<=n; ++i) path[i] = INF;


    H.insert(make_pair(0,1));

    while(!H.empty()){
        int cn = H.begin()->second;
        int cd = H.begin()->first;
        H.erase(H.begin());
        for(int i = 0; i!=nod[cn].size(); ++i){
            int to = nod[cn].at(i).first;
            int cost = nod[cn].at(i).second;
            if(path[to]>path[cn]+cost){
                if(path[to]!=INF){
                    H.erase(H.find(make_pair(path[to],to)));
                }
                path[to] = path[cn] + cost;
                H.insert(make_pair(path[to],to));
            }
        }
    }

    for(int i = 2; i<=n; ++i){
        if(path[i]==INF)path[i] = 0;
        cout<<path[i]<<' ';
    }


    return 0;
}