#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#define inf 1000000
#define nmax 50001
using namespace std;

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

int n, m, dist[nmax];
vector <pair<int, int> > graf[nmax];
priority_queue <pair <int, int> > pq;
bool viz[nmax];

void dijsktra(){

    for(int i = 1; i <= n; ++i)
        dist[i] = inf;
    int start = 1;
    dist[start] = 0;
    pq.push({0, start});

    while(!pq.empty()){

        int nod_curent = pq.top().second;
        pq.pop();

        if(viz[nod_curent] == false){
            viz[nod_curent] = true;
            for(int i = 0; i < graf[nod_curent].size(); ++i){
                int vecin = graf[nod_curent][i].first;
                int cost = graf[nod_curent][i].second;

                if( dist[nod_curent] + cost < dist[vecin]){
                    dist[vecin] = dist[nod_curent] + cost;
                    pq.push( {dist[vecin], vecin} );

                }
            }
        }
    }



}

int main(){

    in >> n >> m;
    for(int i = 1; i <= m; ++i){
        int a, b, cost;
        in >> a >> b >> cost;
        graf[a].push_back({b, cost});
    }
    dijsktra();
    for(int i = 2; i <= n; ++i){
        if(dist[i] == inf)
            out<<0<<' ';
        else
            out<<dist[i]<<' ';
    }

    return 0;
}