#include <cstdio>
#include <vector>
#define NMAX 50001
#define INF 1000000000

using namespace std;
FILE * fin=fopen("dijkstra.in", "r");
FILE * fout=fopen("dijkstra.out", "w");

struct Vecin
{
    int vf;
    short int c;
};

vector <Vecin> G[NMAX];
int n, m, x0 = 1;
int cmin[NMAX], prec[NMAX];
bool z[NMAX];

void citire();
void dijkstra();
void afisare();
int main()
{

    citire();
    dijkstra();
    afisare();
    return 0;
}

void citire()
{
    int i, x, y, c;
    Vecin aux;
    fscanf(fin,"%d%d",&n,&m);
    for(i = 0; i < m; i++)
    {
        fscanf(fin,"%d%d%d",&x,&y,&c);
        aux.vf = y;
        aux.c = c;
        G[x].push_back(aux);
    }
    z[x0] = 1;
    for(i = 1; i <= n; ++i)
    {
        prec[i] = x0;
        cmin[i] = INF;
    }
    prec[x0] = 0;
    cmin[x0] = 0;

    for(i = 0; i < G[x0].size(); ++i)
            cmin[G[x0][i].vf] = G[x0][i].c;
}

void dijkstra()
{
    int i, j, mini, vfmin;
    for(i = 1; i <= n-1; ++i)
    {
        mini = INF;
        //determin un varf selectat de cost minim
        for(j = 1; j <= n; ++j)
            if(z[j] == 0 && cmin[j] < mini)
            {
                mini = cmin[j];
                vfmin = j;
            }
        if(mini == INF)
            break;
        z[vfmin] = 1;
        for(j = 0; j < G[vfmin].size(); ++j)
            if(cmin[G[vfmin][j].vf] > cmin[vfmin]+G[vfmin][j].c)
            {
                cmin[G[vfmin][j].vf] = cmin[vfmin] + G[vfmin][j].c;
                prec[G[vfmin][j].vf] = vfmin;
            }

    }
}

void afisare()
{
    int i;
    for(i = 2; i <= n; ++i)
        if(cmin[i] == INF)
            fprintf(fout, "0 ");
        else
            fprintf(fout, "%d ", cmin[i]);
}