#include <cstdio>
#include <vector>
#define NMAX 50007
#define pb push_back
#define inf 2000000007
#define inf2 2000000009
using namespace std;
FILE *fin, *fout;
struct arc
{
    int vec;
    int cost;
} tmp;
vector<arc> adj[NMAX];
int n, m, x, arb[2*NMAX], dij[NMAX], ans[NMAX], sze, aux = 1;
void update(int st, int dr, int pos, int nod)
{
    if(st == dr)
    {
        arb[nod] = pos;
        return ;
    }
    int mij = (st+dr)/2;
    if(pos <= mij) update(st, mij, pos, 2*nod);
    if(pos > mij) update(mij+1, dr, pos, 2*nod+1);
    arb[nod] = (dij[arb[2*nod]] < dij[arb[2*nod + 1]])? arb[2*nod]: arb[2*nod+1];
    return ;
}
void citire()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; ++i)
    {
        scanf("%d %d %d", &x, &tmp.vec, &tmp.cost);
        adj[x].pb(tmp);
    }
}
void init()
{
    for(int i = 1; i<= n; ++i)
    {
        dij[i] = inf;
        update(1, n, i, 1);
    }
    dij[1] = 0;
}
void dijkstra()
{
    for(int i = 1; i<= n; ++i)
    {
        sze = adj[aux].size();
        for(int j = 0; j< sze; ++j)
        {
            if(dij[adj[aux][j].vec] == inf2) continue;
            if(dij[adj[aux][j].vec] > dij[aux] + adj[aux][j].cost) dij[adj[aux][j].vec] = dij[aux] + adj[aux][j].cost;
            update(1, n, adj[aux][j].vec, 1);
        }
        ans[aux] = dij[aux];
        dij[aux] = inf2;
        update(1, n, aux, 1);
        aux = arb[1];
    }
    for(int i = 1; i<= n; ++i) if(ans[i] == inf) ans[i] = 0;
}
void afisare()
{
    for(int i = 2; i<= n; ++i) printf("%d ", ans[i]);
    printf("\n");
}
int main()
{
    fin = freopen("dijkstra.in", "r", stdin);
    fout = freopen("dijkstra.out", "w", stdout);
    citire();
    init();
    dijkstra();
    afisare();
    fclose(fin);
    fclose(fout);
    return 0;
}