#include <iostream>
#include <stdio.h>
#define n 50001

using namespace std;

int M, N, v, **a, s[n], t[n], d[n];


int kmin()
{
    int min = 1001, k = 1001;
    for(int i=1; i<=N; i++)
        if(s[i] == 0 && d[i]<min && d[i]>0)
        {
            min = d[i];
            k = i;
        }
    return k;
}

void dijkstra()
{
    int k = kmin();
    while(k!= -1 && k <= N)
    {
        s[k] = 1;
        for(int i=1; i<=N; i++)
            if(s[i] == 0 && d[i] > d[k] + a[k][i])
                {
                    d[i] = d[k] + a[k][i];
                    t[i] = k;
                }
        k = kmin();
    }
}

void afisare()
{
    for(int i=2; i<=N; i++)
        printf("%d ", d[i]);
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &N, &M);

    a = new int*[N];
    for(int i=1; i<=N; i++)
        a[i] = new int[N];

    for(int i=0; i<M; i++)
            {
                int x, y;
                int t;
                scanf("%d%d%d", &x, &y, &t);
                a[x][y] = t;

            }
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            if(!a[i][j] )
                a[i][j] = 50001;

    //init
    v = 1;
    for(int i=1; i<=N; i++)
    {
        s[i] = 0;
        d[i] = a[v][i];
        if(d[i]!=0 && d[i] < 1001 && d[i] > 0)
            t[i] = v;
        s[v] = 1;
    }

    dijkstra();
    afisare();

    for(int i=1; i<=N; i++) delete a[i];
    delete []a;
    printf("\n");
    return 0;
}