#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 50001
using namespace std;
FILE *fin, *fout;
const int inf=1<<30;
struct lista {
    int vf, c;
}aux;
struct varf {
    int vf, c;
    bool operator< (varf &xx) { return c>xx.c; }
}auxh;
vector <lista> graf[NMAX];
vector <varf> heap;
int dist[NMAX];
bool sel[NMAX];
int n, m;
int main()
{
    int i, e, a, b, c, vf, ax;
    fin=fopen("dijkstra.in", "r"); fout=fopen("dijkstra.out", "w");
    fscanf (fin, "%d%d", &n, &m);
    for (i=1; i<=m; ++i) { fscanf (fin, "%d%d%d", &a, &b, &c); aux.vf=b; aux.c=c; graf[a].push_back(aux); }
    for (i=1; i<=n; ++i) dist[i]=inf; dist[1]=1; sel[1]=1;
    for (i=0; i<graf[1].size(); ++i) { dist[graf[1][i].vf]=graf[1][i].c; auxh.c=graf[1][i].c; auxh.vf=graf[1][i].vf; heap.push_back(auxh); }
    make_heap(heap.begin(), heap.end());
    for (e=1; e<n; ++e) {
        //scot varful din heap
        auxh=heap.front(); pop_heap(heap.begin(), heap.end()); heap.pop_back(); vf=auxh.vf;
        sel[vf]=1;
        //ii optimizez adiacentii
        for (i=0; i<graf[vf].size(); ++i) if (!sel[graf[vf][i].vf]) {
            ax=dist[vf]+graf[vf][i].c;
            if (ax<dist[graf[vf][i].vf]) {
                //actualizez distanta
                dist[graf[vf][i].vf]=ax;
                //inserez varful in heap
                auxh.vf=graf[vf][i].vf; auxh.c=dist[graf[vf][i].vf];
                heap.push_back(auxh); push_heap(heap.begin(), heap.end());
            }
        }
    }
    for (i=2; i<=n; ++i)
        if (dist[i]!=inf) fprintf (fout, "%d ", dist[i]); else fprintf (fout, "0 ");
    fprintf (fout, "\n");
    fclose(fin); fclose(fout);
    return 0;
}