#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000

int N, M, Q[1<<20], inc, sf; vector<int> G[MAXN], C[MAXN];
int d[MAXN];

int main(void)
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    int i, j, k, a, b, c;

    scanf("%d %d\n", &N, &M);
    for(i = 1; i <= M; i++)
        scanf("%d %d %d", &a, &b, &c), G[a].pb(b), C[a].pb(c);

    for(i = 1; i <= N; i++) d[i] = INF;
    
    Q[inc = sf = 0] = 1, d[1] = 0;
    while(inc <= sf)
    {
        a = Q[inc++];
        for(i = 0; i < G[a].size(); i++)
         if( d[ G[a][i] ] > d[a] + C[a][i] )
            d[ G[a][i] ] = d[a] + C[a][i], Q[++sf] = G[a][i];
    }

    for(i = 2; i <= N; i++)
        printf("%d ", d[i] == INF ? 0 : d[i]);

    return 0;
}