#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define maxN 50005
#define inf (1 << 30)
#define PB push_back
#define MKP make_pair
#define f first
#define s second

int Cost[maxN];
bool Viz[maxN];
vector < pair <int, int> > List[maxN];
int H[maxN], Poz[maxN], dim;



void push (int nod)
{
    if (nod == 1) return;
    if (Cost[H[nod]] >= Cost[H[nod / 2]]) return;

    swap (H[nod], H[nod / 2]);
    swap (Poz[H[nod]], Poz[H[nod / 2]]);

    push (nod / 2);
}


void pop (int nod)
{
    int f1 = nod * 2, f2 = nod * 2 + 1;
    int nodmin = nod;

    if (f1 <= dim && Cost[H[f1]] < Cost[H[nodmin]]) nodmin = f1;
    if (f2 <= dim && Cost[H[f2]] < Cost[H[nodmin]]) nodmin = f2;

    if (nod == nodmin) return;

    swap (H[nod], H[nodmin]);
    swap (Poz[H[nod]], Poz[H[nodmin]]);

    pop (nodmin);
}


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

    int N, M;
    scanf ("%d %d", &N, &M);

    while (M --)
    {
        int x, y, z;
        scanf ("%d %d %d", &x, &y, &z);

        List[x].PB ( MKP (y, z) );
    }

    H[++ dim] = 1;
    Poz[1] = 1;

    for (int i = 2; i <= N; ++ i)
    {
        H[++ dim] = i;
        Poz[i] = dim;
        Cost[i] = inf;
    }

    for (int i = 1; i <= N; ++ i)
    {
        int nod = H[1];
        Viz[nod] = true;

        swap (H[1], H[dim]);
        swap (Poz[H[1]], Poz[H[dim]]);
        -- dim;
        pop (1);

        for (int j = 0; j < List[nod].size(); ++ j)
        {
            int nod2 = List[nod][j].f, c2 = List[nod][j].s;

            if (Viz[nod2]) continue;
            if (Cost[nod2] <= Cost[nod] + c2) continue;

            Cost[nod2] = Cost[nod] + c2;

            int poz_h = Poz[nod2];

            if (Cost[H[poz_h]] <= Cost[H[poz_h / 2]]) push (poz_h);
            else pop (poz_h);
        }
    }

    for (int i = 2; i <= N; ++ i)
        if (Cost[i] == inf) printf ("0 ");
        else printf ("%d ", Cost[i]);

    return 0;
}