#include <stdio.h>
#include <vector>
#define NMAX 100023
#define inf 2000000023
#define inf2 2000000025
FILE *fin, *fout;
int n, m, x, arb[2*NMAX+1], dij[NMAX], ans[NMAX], p = 1, viz[NMAX], sizen;
int min(int a, int b)
{
    return (a<b)?a:b;
}
struct arc
{
    int vec;
    int cost;
} temp;
std::vector<arc> adj[NMAX];
void pun(int st, int dr, int pos, int nod)
{
    if(st == dr)
    {
        arb[nod] = pos;
        return;
    }
    int mij = (st+dr)/2;
    if(pos <= mij) pun(st, mij, pos, 2*nod);
    else pun(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;
}
int main()
{
    fin = freopen("dijkstra.in", "r", stdin);
    fout = freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 0; i< m; i++)
    {
        scanf("%d%d%d", &x, &temp.vec, &temp.cost);
        adj[x].push_back(temp);
    }
    for(int i = 1; i<= n; i++)
    {
        dij[i] = inf;
        pun(1, n, i, 1);
    }
    viz[1] = 1;
    dij[1] = 0;
    for(int u = 0;u< n;u++)
    {
        sizen = adj[p].size();
        for(int i = 0; i< sizen; i++)
        {
            if(dij[adj[p][i].vec] == inf2) continue;
            dij[adj[p][i].vec] = min(dij[adj[p][i].vec], dij[p] + adj[p][i].cost);
            pun(1, n, adj[p][i].vec, 1);
        }
        ans[p] = dij[p];
        dij[p] = inf2;
        pun(1, n, p, 1);
        p = arb[1];
    }
    for(int i = 2; i<= n; i++) if(ans[i] == inf) ans[i] = 0;
    for(int i = 2; i<= n; i++) printf("%d ", ans[i]);printf("\n");
    fclose(fin);
    fclose(fout);
    return 0;
}