#include <cstdio>
#include <vector>
#define NMAX 50001
#define INF 1000000000
using namespace std;

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

vector <Vecin> G[NMAX];
int n, 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 m, i, x;
    int lg;
    struct Vecin aux;
    FILE*fin=fopen ("dijkstra.in", "r");
    fscanf(fin, "%d %d", &n, &m);
    for (i=1; i<=m; ++i)
    {
        fscanf(fin, "%d %d %hd", &x, &aux.vf, &aux.cost);
        G[x].push_back (aux);
    }

    for (i=2; i<=n; ++i)
    {
        cmin[i]=INF;
        //prec[i]=1;
    }
    Z[1]=true;
    lg=G[1].size();
    for (i=0; i<lg; ++i)
        cmin[G[1][i].vf]=G[1][i].cost;
    fclose(fin);
    return;
}

void Dijkstra()
{
    int i, j, vfmin, minimus;
    int lg;
    for (i=1; i<=n-1; ++i)
    {
        minimus=INF;
        for (j=2; j<=n; ++j)
            if (!Z[j] && cmin[j]<minimus)
        {
            minimus=cmin[j];
            vfmin=j;
        }

        Z[vfmin]=true;
        lg=G[vfmin].size();
        for (j=0; j<lg; ++j)
            if (!Z[G[vfmin][j].vf] && cmin[G[vfmin][j].vf]>cmin[vfmin]+G[vfmin][j].cost)
        {
            cmin[G[vfmin][j].vf]=cmin[vfmin]+G[vfmin][j].cost;
            //prec[G[vfmin][j].vf]=vfmin;
        }
    }
    return;
}

void afisare()
{
    FILE*fout=fopen ("dijkstra.out", "w");
    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);
    return;
}