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

#define PII pair <int, int>
#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000
# define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0
const int hg = 1 << 13;
int poz, N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
priority_queue <PII, vector <PII>, greater<PII> > T;

char ch[hg];

inline void cit ( int &x ) {
    int semn = 1;
    if ( ch[0] == '\0' ) fread ( ch, 1, hg, stdin ) ;
    else for ( ; (ch[poz] < '0' || ch[poz] > '9') && ch[poz] != '-' ; verf ) ;
    for ( x = 0 ; ch[poz] >= '0' && ch[poz] <= '9' || ch[poz] == '-' ; (ch[poz] == '-' ? semn = -1 : x = x * 10 + ch[poz] - '0'), verf ) ;
    x *= semn;
}

void solve(void)
{
    int i, j, k, val, x;

    for(i = 2; i <= N; i++) d[i] = INF;
    T.push( mp(0, 1) );

    while( T.size() > 0 )
    {
        val = (T.top()).first, x = (T.top()).second;
        T.pop();
        for(i = 0; i < G[x].size(); i++)
         if(d[ G[x][i] ] > val + C[x][i] )
            d[ G[x][i] ] = val + C[x][i], T.push(mp(d[G[x][i]],G[x][i]));
    }
}

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

    int i, a, b, c;

    cit (N), cit (M);

    for(i = 1; i <= M; i++)
        cit (a), cit (b), cit (c), G[a].pb(b), C[a].pb(c);

    solve();

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

    return 0;
}