#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#define nmax 50005
#define inf 1<<30
#define cost first
#define ind second
using namespace std;
 
int n, m, best[nmax];
bool vizitat[nmax];
 
vector <int> vecin[nmax], muchie[nmax];
set <pair <int, int> > q;
 
void dijkstra() {
    pair <int, int> nod;
    int curent, nou, costcurent, potential;
 
    while(!q.empty()) {
        nod = *q.begin();
        q.erase( *q.begin() );
     
        curent = nod.ind;   
        costcurent = best[curent];
        vizitat[curent] = true;
 
        for(int i=0; i < vecin[curent].size(); i++) {			//iau toti vecinii nevizitati ai nodului curent
            nou = vecin[curent][i]; 
            if(vizitat[nou]) continue;
             
            potential = costcurent + muchie[curent][i];			//distanta minima pana la nodul curent + lungimea muchiei dintre curent si vecin
            if(potential < best[nou]) {      
		q.erase( make_pair(best[nou], nou) );
                best[nou] = costcurent + muchie[curent][i];		//daca distanta potentiala-i de preferat, atunci actualizez bestul
                q.insert( make_pair( best[nou], nou ) );		//si introduc in set noul vecin obtinut
            }
        }
     
    }
}       
         
 
int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
     
    int i, j, a, b, c;
 
    f>>n>>m;
    for(i=1; i<=m; i++) {
        f>>a>>b>>c;
        vecin[a].push_back(b);      //adaug indicele vecinului
        muchie[a].push_back(c);     //si in acelasi timp si lungimea muchiei
    }
    best[1] = 0;
    for(i=2; i<=n; i++) best[i] = inf, vizitat[i] = false;
 
    q.insert( make_pair(0, 1) );        //introduc nodul sursa in heap
    dijkstra();
 
    for(i=2; i<=n; i++) 
        if(best[i]==inf) g<<"0 ";
        else g<<best[i]<<" ";
    g<<"\n";
 
 
    return 0;
}