#include <iostream>
#include <vector>
#include <stdio.h>
#include <cstring>

const int MASK = 65535;
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[MASK+1];
bool Present[50001];

char buff[MASK];
int pos;

void reader (int* nr) {
    while(buff[pos] < '0' || buff[pos] > '9') {
        pos++;
        if (pos == MASK) {
            fread (buff, 1, MASK, stdin);
            pos = 0;
        }
    }

    int temp = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9') {
        temp = temp * 10 + (buff[pos] - '0');
        pos++;
        if (pos == MASK) {
            fread (buff, 1, MASK, stdin);
            pos = 0;
        }
    }

    *nr = temp;
}

int main () {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    fread (buff, 1, MASK, stdin);

    int Noduri, Muchii;
    reader(&Noduri);
    reader(&Muchii);

    for (int i = 0; i < Muchii; i++) {
        int orig, dest, cost;
        reader(&orig);
        reader(&dest);
        reader(&cost);

        heaplevel++;
        prevy[heaplevel] = nod[orig];
        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 & MASK];
        int ind = nod[analyze];
        while (ind) {
            if (Paths[muchii[ind].Vec] > Paths[analyze] + muchii[ind].Cost) {
                if (Present[muchii[ind].Vec] == false) {
                    Present[muchii[ind].Vec] = true;
                    Chain[(++Fin) & MASK] = muchii[ind].Vec;
                }
                Paths[muchii[ind].Vec] = Paths[analyze] + muchii[ind].Cost;
            }
            ind = prevy[ind];
        }
        Present[analyze] = false;
        St++;
    }
    ///MACHINE LEARNING CODE SECTION END

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