#include <stdio.h>

using namespace std;

int n, m, d[50001], viz[50001], p[50001];

struct muchie
{
    int x, y, c;
}mu[250001];

void citire()
{
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; i++)
        scanf("%d %d %d", &mu[i].x, &mu[i].y, &mu[i].c);
}

void init()
{
    for (int i=2; i<=n; i++)
        d[i]=100000;
}

void bellman_ford()
{
    p[1]=1;
    for (int i=1; i<n; i++)
        for (int j=0; j<m; j++)
            if (d[mu[j].x]!=100000)
                if (d[mu[j].x]+mu[j].c<d[mu[j].y])
                {
                    d[mu[j].y]=d[mu[j].x]+mu[j].c;
                    p[mu[j].y]=p[mu[j].x];
                }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    citire();
    init();
    bellman_ford();
    for (int i=2; i<=n; i++)
        if (p[i]==0)
            printf("%d ", 0);
        else
            printf("%d ", d[i]);
    return 0;
}