#include <fstream>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

int N,M;
vector <pair<int,int> > V[50020];

class Heap{

private:
    pair<int,int> H[200011];
    int N;
    int parent(int x){
        return x/2;
    }

    int left_son(int x){
        return 2 * x ;
    }

    int right_son(int x){
        return 2 * x + 1;
    }
    void go_down(int pos){
        int maxl = pos;

        if (left_son(pos) <= N && H[left_son(pos)].second <= H[pos].second){
            maxl = left_son(pos);
        }

        if (right_son(pos) <= N && H[right_son(pos)].second <= H[maxl].second){
            maxl = right_son(pos);
        }

        if (maxl != pos){
            swap(index[H[maxl].first],index[H[pos].first]);
            swap (H[maxl],H[pos]);
            go_down(maxl);
        } else return ;

    }

    void go_up(int pos){
        if (pos == 1 ) return ;
        if (H[pos].second < H[parent(pos)].second){
            swap(index[H[pos].first],index[H[parent(pos)].first]);
            swap(H[pos], H[parent(pos)]);
            go_up(parent(pos));
        }else return ;
    }


public:
    map <int,int> index;
    Heap(){
        N = 0;
    }
    pair<int,int> get_min(){
        return H[1];
    }
    void add(pair<int,int> value){
        H[++N] = value;
        index[value.first] = N;
        go_up(N);
    }
    void pop(){
        index[H[1].first] = -1;
        swap(H[1],H[N--]);
        go_down(1);
    }
    bool isempty(){
        return N == 0;
    }
    void update(int key, int newv){
        H[index[key]].second = newv;
        go_up(index[key]);
    }
    pair<int,int> getel(int pos){
        return H[pos];
    }


};
Heap h;


void dijkstra(int beg){
    int drum[50020];
    for (int i = 1;i<=N;i++) drum[i] = 1e9,h.index[i] = -1;
    drum[1] = 0;
    h.index[1] = 0;
    h.add(make_pair(1,0));
    for (int i = 2; i <= N;i++) h.add(make_pair(i,1e9));
    //h.update(5,10);

    while(!h.isempty()){

        pair<int,int> minl = h.get_min();
//        cout << minl.first <<" "<<minl.second <<endl;
//        for (int i = 1 ;i <= N ;i++) cout <<i<<" "<<h.index[i]<<" "<<h.getel(h.index[i]).second<<endl;
//        cout <<endl;
        drum[minl.first] = minl.second;
        h.pop();

        for (auto it:V[minl.first]){
            if (h.getel(h.index[it.first]).second > it.second + drum[minl.first] && h.index[it.first] != -1){

                drum[it.first] = it.second+ drum[minl.first];
                h.update(it.first, drum[it.first]);

            }

        }

    }
    ofstream fout("dijkstra.out");
    for (int i = 2; i <= N;i++) if (drum[i] == 1e9) fout <<0<<" ";
    else fout <<drum[i]<<" ";
}

int main()
{

    ifstream fin("dijkstra.in");

    fin >>N>>M;
    int a,b,c;
    for (int a,b,c; M--;){
        fin >>a>>b>>c;
        V[a].push_back(make_pair(b,c));
    }
    dijkstra(1);
//    int x;
//    int k = 1;
//    while (fin >> x){
//        h.add(make_pair(x,k++));
//
//    }
//    while (!h.isempty()){
//        cout << h.get_min().first<<" "<<h.get_min().second<<endl;
//        h.pop();
//    }
    return 0;
}