#include <cstdio>
#include <vector>
#define DMAX 50002
#define INF 1000000000

using namespace std;

FILE * fin=fopen("dijkstra.in", "r");

FILE * fout=fopen("dijkstra.out", "w");

struct vecin
{
int vf;
int c;
};
vector<vecin>G[DMAX];

int n, m, x0=1;
int cmin[DMAX], prec[DMAX];
bool Z[DMAX];

void citire();
void init();
void Djkstra();
void write();

int main()
{
    citire();
    init();
    Djkstra();
    write();
return 0;
}

void Djkstra()
{
    int i, j, vfmin, cost;
    for (i=1; i<=n-1; i++)
    {
        // caut minimul
        vfmin=n+1;
        cost=INF;
        for (j=1; j<=n; j++)
            if (!Z[j] && cmin[j]<cost)
            {
                cost=cmin[j];
                vfmin=j;
            }
        if (vfmin==n+1)
            return;
        Z[vfmin]=1;
        for(j=0; j<G[vfmin].size(); ++j)
            if(!Z[G[vfmin][j].vf] && (cmin[vfmin]+G[vfmin][j].c<cmin[G[vfmin][j].vf]))
            {
                cmin[G[vfmin][j].vf]=cmin[vfmin]+G[vfmin][j].c;
                prec[G[vfmin][j].vf]=vfmin;
            }
    }
}

void init()
{
    int i;
    Z[x0]=1;
    for(i=1; i<=n; i++)
    {
        prec[i]=i;
        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 write()
{
    int i;
    for(i=2; i<=n; i++)
        if(cmin[i]==INF)
            fprintf(fout, "0 ");
        else
            fprintf(fout, "%d ", cmin[i]);
    fprintf(fout, "\n");
    fclose(fout);
    }

void citire()
{
    int i, x, y;
    vecin v;
    fscanf(fin, "%d %d", &n, &m);
    for (i=1; i<=m; i++)
    {
        fscanf(fin, "%d %d %d", &x, &y, &v.c);
        v.vf=y;
        G[x].push_back(v);
    }
}