#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]) {
                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;
}