#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int INF=999999999;

int main(){
    ifstream reader("dijkstra.in");
    ofstream writer("dijkstra.out");

    int n,m;
    reader>>n>>m;

    vector< vector <pair<int,int> > > graf(n+1);

    for(int i=0; i<m; i++){
        int A,B,C;
        reader>>A>>B>>C;
        graf[A].push_back(make_pair(B,C));
    }

    vector<int> dist(n+1,INF);
    dist[1]=0;

    priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > coada;

    coada.push(make_pair(0,1));

    while(!coada.empty()){
        int distCurenta=coada.top().first;
        int nodCurent=coada.top().second;
        coada.pop();

        if(distCurenta != dist[nodCurent]) 
            continue;

        for(int i=0; i<graf[nodCurent].size(); i++){
            int vecin = graf[nodCurent][i].first;
            int cost = graf[nodCurent][i].second;

            if(distCurenta+cost < dist[vecin]){
                dist[vecin] = distCurenta+cost;
                coada.push(make_pair(dist[vecin],vecin));
            }
        }
    }

    for(int i=2; i<=n; i++){
        if(dist[i] == INF) 
            writer<<0;
        else 
            writer<<dist[i];
        if(i<n) 
            writer<<" ";
    }

    return 0;
}