#include <cstdio>

#define dim 50005
#define inf 0x3f3f3f3f

int N;
int M;

int P[dim];
int D[dim];
int Pos[dim];

struct Nod
{
    int n;
    int c;
    Nod *next;

} *G[dim];

inline int Dup(int i)
{
    return
            (i << 1);
}

void Add(Nod *& g, int n, int c)
{
    Nod *p = new Nod;
    p -> n = n;
    p -> c = c;
    p -> next = g;
    g = p;
}

void ReadData()
{
    freopen("dijkstra.in", "rt", stdin);

    int i, a, b, c;
    for(scanf("%d %d", &N, &M), i=1; i<=M; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        Add(G[a], b, c);
    }

    fclose(stdin);
}

void Swap(int i, int j)
{
    int t = Pos[P[i]];
    Pos[P[i]] = Pos[P[j]];
    Pos[P[j]] = t;

    t = P[i];
    P[i] = P[j];
    P[j] = t;
}

void HeapUp(int k)
{
    if(k <= 1) return;
    int t = k >> 1;

    if(D[P[t]] > D[P[k]])
    {
        Swap(t, k);
        HeapUp(t);
    }
}

void Restore(int r, int b)
{
    if(Dup(r) <= b)
    {
        int st = D[P[Dup(r)]];
        int dr;

        if(Dup(r) + 1 <= b)
            dr = D[P[Dup(r)+1]];
        else
            dr = st + 1;

        int x;

        if(st < dr) x = Dup(r);
        else x = Dup(r) + 1;

        if(D[P[r]] > D[P[x]])
        {
            Swap(r, x);
            Restore(x, b);
        }
    }
}

void Dijkstra()
{
    Nod *p;
    int i;

    for(i=2; i<=N; ++i) D[i] = inf, P[i] = i, Pos[i] = i;
    D[1] = 0;
    P[1] = 1;

    for(p=G[1]; p; p=p->next)
        D[p->n] = p->c;

    for(i=2; i<=N; ++i)
        HeapUp(i);

    for(i=N; i>1; --i)
    {
        int nd;
        for(p=G[nd=P[1]]; p; p=p->next)
            if(D[p->n] > D[nd] + p->c)
            {
                D[p->n] = D[nd] + p->c;
                HeapUp(Pos[p->n]);
            }

        Swap(1, i);
        Restore(1, i-1);
    }
}

void WriteSolution()
{
    freopen("dijkstra.out", "wt", stdout);

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

    fclose(stdout);
}

int main()
{
    ReadData();
    Dijkstra();
    WriteSolution();

    return 0;
}