#include <fstream>
#include <cstdio>
#include <vector>
#define NMAX 50001
#define MMAX 250000
#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, x0=1;
int cmin[NMAX], prec[NMAX];
bool z[NMAX];

void citire_init();
void dijkstra();
void afisare();

int main()
{
    citire_init();
    dijkstra();
    afisare();
    return 0;
}
void citire_init()
{
    int i, m, 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, vfmin, costminim=0;
    for(i=1; i<=n-1; i++)
        {
        //determin vf neselectat de cost minim
        costminim=INF;
        for (j=1; j<=n; j++)
            {
            if(cmin[j]<costminim && z[j]==0)
                {
                vfmin=j;
                costminim=cmin[j];
                }
            }
        if(costminim==INF) break;
        //selectez
        z[vfmin]=1;
        //parcurg lista de adiacenta a lui vfmin
        for (j=0; j<g[vfmin].size(); j++)
            if(z[g[vfmin][j].vf]==0 && 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]);
}