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

ifstream fin("dijkstra.in");
ofstream fout("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(){

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