#include <bits/stdc++.h>

using namespace std;

bool viz[500005];

struct my_comp{
    bool operator()(pair<int, int> &a, pair<int, int> &b){
        return a.second > b.second;
    }
};
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int N, M;
    cin>>N>>M;
    int const MAX_VAL = -1;
    vector<int> cost;
    vector<pair<int, int> > edges[N+1];
    int source, target, value;
    pair<int, int> current, newp;
    cost.push_back(0);
    for(int i=1; i<=N; i++){
        cost.push_back(-1);
    }
    for(int i=1; i<=M; i++){
        cin>>source;
        cin>>target;
        cin>>value;
        current = {target, value};
        edges[source].push_back(current);
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, my_comp > pq;

    int so_far = 0;

    so_far ++;
    viz[1] = true;
    for(int i=0; i<edges[1].size(); i++){
        pq.push(edges[1][i]);
    }

    while(pq.empty() != true && so_far < N){
        do{
        current = pq.top();
        pq.pop();
        }while(viz[current.first] == true && !pq.empty());

        so_far++;
        target = current.first;
        if(viz[target] == true){
            continue;
        }
        viz[target] = true;
        cost[target] = current.second;
        for(int j=0; j<edges[target].size(); j++){
            newp = edges[target][j];
            if(viz[newp.first] == false){
                newp.second += cost[target];
                pq.push(newp);
            }
        }
    }

    for(int i=2; i<=N; i++){
        if(cost[i] == -1)
            cout<<"0 ";
        else
            cout<<cost[i]<<" ";
    }
    cout<<'\n';
    return 0;
}