#include <iostream>
#include <vector>
#include <stdio.h>
#include <cstring>
using namespace std;

class Muchie {
public:
    int Vec;
    int Cost;
    Muchie () {}
    Muchie (int v, int c) {
        Vec = v;
        Cost = c;
    }
};

int nod[50001], prevy[250001];
int heaplevel;
Muchie muchii[250001];

int Paths[50001];

int Chain[250001];

int main () {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int Noduri, Muchii;
    scanf("%d%d", &Noduri, &Muchii);

    for (int i = 0; i < Muchii; i++) {
        int orig, dest, cost;
        scanf("%d%d%d", &orig, &dest, &cost);

        heaplevel++;

        if (nod[orig] == 0)
            nod[orig] = heaplevel;
        else
            prevy[nod[orig]] = heaplevel;

        /*prevy[heaplevel] = nod[orig];
        muchii[heaplevel] = Muchie(dest, cost);
        nod[orig] = heaplevel;*/

        muchii[heaplevel] = Muchie(dest, cost);
    }

    memset(Paths, 'G', (Noduri + 1) * 4);
    Paths[1] = 0;

    ///MACHINE LEARNING CODE SECTION START
    int St = 1;
    int Fin = 1;
    Chain[St] = 1;

    while (St <= Fin) {
        int analyze = Chain[St % 250001];
        int ind = nod[analyze];
        while (ind) {
            if (Paths[muchii[ind].Vec] > Paths[analyze] + muchii[ind].Cost) {
                Chain[(++Fin) % 250001] = muchii[ind].Vec;
                Paths[muchii[ind].Vec] = Paths[analyze] + muchii[ind].Cost;
            }
            ind = prevy[ind];
        }
        St++;
    }
    ///MACHINE LEARNING CODE SECTION END

    for (int destin = 2; destin <= Noduri; destin++) {
        if (Paths[destin] > 1000000000)
            printf("0 ");
        else
            printf("%d ", Paths[destin]);
    }
}