#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 H[maxN], PozH[maxN], dim;
int Cost[maxN];
bool Viz[maxN];
vector < pair <int, int> > List[maxN];


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

    swap (H[nod], H[nod / 2]);
    swap (PozH[H[nod]], PozH[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[nodmin]] > Cost[H[f1]]) nodmin = f1;
    if (f2 <= dim && Cost[H[nodmin]] > Cost[H[f2]]) nodmin = f2;

    if (nodmin == nod) return;

    swap (H[nod], H[nodmin]);
    swap (PozH[H[nod]], PozH[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, c;
        scanf ("%d %d %d", &x, &y, &c);

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

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

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

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

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

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

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

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

            int pos = PozH[nod2];

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

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

    return 0;
}