#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], prev[250001];
int heaplevel;
Muchie muchii[250001];

int Paths[50001];

int Chain1[250001];
int Chain1Level;
int Chain2[250001];
int Chain2Level;
bool ChooseChain; //Double Lord Helix Implementation

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 {
            prev[nod[orig]] = heaplevel;
        }

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

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

    Chain1Level = 0;
    Chain2Level = 0;
    int ind = nod[1];

    while (ind != 0) {
        Chain1[Chain1Level++] = muchii[ind].Vec;
        Paths[muchii[ind].Vec] = muchii[ind].Cost;
        ind = prev[ind];
    }

    ChooseChain = false;
    while (true) {
        if (ChooseChain) {
            if (Chain2Level == 0)
                break;
            for (int i = 0; i < Chain2Level; i++) {
                int vecin = Chain2[i];
                int ind = nod[vecin];
                while (ind != 0) {
                    if (Paths[muchii[ind].Vec] > Paths[vecin] + muchii[ind].Cost) {
                        Paths[muchii[ind].Vec] = Paths[vecin] + muchii[ind].Cost;
                        Chain1[Chain1Level++] = muchii[ind].Vec;
                    }
                    ind = prev[ind];
                }
            }
            Chain2Level = 0;
        } else {
            if (Chain1Level == 0)
                break;
            for (int i = 0; i < Chain1Level; i++) {
                int vecin = Chain1[i];
                int ind = nod[vecin];
                while (ind != 0) {
                    if (Paths[muchii[ind].Vec] > Paths[vecin] + muchii[ind].Cost) {
                        Paths[muchii[ind].Vec] = Paths[vecin] + muchii[ind].Cost;
                        Chain2[Chain2Level++] = muchii[ind].Vec;
                    }
                    ind = prev[ind];
                }
            }
            Chain1Level = 0;
        }
        ChooseChain = !ChooseChain;
    }

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