#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#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]; /// graf[i].first = vecin, graf[i].second = cost
priority_queue <pair <int, int> > pq;
/// coada cu prioritate: la fiecare introducere, introduc distanta * -1 pentru ca
///                      elementele sa fie "crescatoare"
bool viz[nmax];

void dijsktra(){

    /// initializez cu infinit distantele
    for(int i = 1; i <= n; ++i)
        dist[i] = inf;

    /// fixez si introduc startul in pr. queue
    int start = 1;
    dist[start] = 0;
    pq.push({0, start});

    while(!pq.empty()){

        /// iau nodul cu distanta cea mai mica din pr.queue ( pq.top() )
        int nod_curent = pq.top().second;
        pq.pop();

        /// il scot, pentru ca l-am retinut, verific daca e deja vizitat si ii parcurg vecinii
        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; /// graf: pair < nod, cost >
                int cost = graf[nod_curent][i].second;

                /// formula de verificare a costului
                if( dist[nod_curent] + cost < dist[vecin]){
                    dist[vecin] = dist[nod_curent] + cost;
                    pq.push( {-dist[vecin], vecin} ); /// pq: pair < dist_to_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}); /// graf orientat
    }
    dijsktra();
    for(int i = 2; i <= n; ++i){
        if(dist[i] == inf)
            out<<0<<' ';
        else
            out<<dist[i]<<' ';
    }
    return 0;
}