#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 read();
void init();
void Djkstra();
void write();

int main()
{
read();
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 read()
{
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);
    }
}