#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50004
#define INF 1000000000

using namespace std;

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

int n, m, x0;

struct intfictiv {int val;};//ca sa pot supraincarca operatorul

int cmin[NMAX];
bool uz[NMAX];//uz[x]=1 dupa ce l-am scos pe x din heap

bool operator < (intfictiv a, intfictiv b)
{
    return cmin[a.val]>cmin[b.val];//ordonez crescator dupa distanta
}
priority_queue <intfictiv> Heap;//implicit max-heap

struct vecin
{
    intfictiv varf;
    intfictiv cost;
};
vector <vecin> A[NMAX];//listele de vecini

void citire();
void dijkstra();
void initializare();
void afisare();

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}

void citire()
{
    int i, x, y, c;
    vecin v;
    fscanf(fin, "%d %d\n", &n, &m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin, "%d %d %d\n", &x, &y, &c);

        v.varf.val=y; v.cost.val=c;
        A[x].push_back(v);
    }

    x0=1;
    initializare();
}

void initializare()
{
    int i, lg;

    for(i=1;i<=n;i++)
        cmin[i]=INF;

    cmin[x0]=0; uz[x0]=1;

    lg=A[x0].size();
    for(i=0;i<lg;i++)
    {
        cmin[A[x0][i].varf.val]=A[x0][i].cost.val;
        Heap.push(A[x0][i].varf);
    }
}

void dijkstra()
{
    int i, j, lg;
    intfictiv minim;
    uz[0]=1;

    while(!Heap.empty())
    {
        minim.val=0;
        while(!Heap.empty() && uz[minim.val])
        {
            minim=Heap.top();
            Heap.pop();
        }

        uz[minim.val]=1;

        lg=A[minim.val].size();
        for(j=0;j<lg;j++)
            if(!uz[A[minim.val][j].varf.val] && cmin[A[minim.val][j].varf.val]>cmin[minim.val]+A[minim.val][j].cost.val)
            {
                cmin[A[minim.val][j].varf.val]=cmin[minim.val]+A[minim.val][j].cost.val;
                Heap.push(A[minim.val][j].varf);
            }
    }
}

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

/*

FARA HEAP - 50p

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

using namespace std;

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

int n, m, x0;
struct vecin
{
    int varf;
    int cost;
};
vector <vecin> A[NMAX];
int cmin[NMAX], prec[NMAX];
bool Z[NMAX];

void citire();
void dijkstra();
void initializare();
void afisare();

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}

void citire()
{
    int i, x, y, c;
    vecin v;
    fscanf(fin, "%d %d\n", &n, &m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin, "%d %d %d\n", &x, &y, &c);

        v.varf=y; v.cost=c;
        A[x].push_back(v);
    }

    x0=1;
    initializare();
}

void initializare()
{
    int i, lg;

    for(i=1;i<=n;i++)
    {
        cmin[i]=INF;
        prec[i]=x0;
    }
    cmin[x0]=0; prec[x0]=0; Z[x0]=1;

    lg=A[x0].size();
    for(i=0;i<lg;i++)
        cmin[A[x0][i].varf]=A[x0][i].cost;
}

void dijkstra()
{
    int i, j, lg;
    int minim;

    cmin[0]=INF;

    for(i=2;i<=n;i++)
    {
        minim=0;
        for(j=1;j<=n;j++)
            if(!Z[j] && cmin[j]<cmin[minim])
                minim=j;

        if(!minim)
            return;

        Z[minim]=1;

        lg=A[minim].size();
        for(j=0;j<lg;j++)
            if(!Z[A[minim][j].varf] && cmin[A[minim][j].varf]>cmin[minim]+A[minim][j].cost)
            {
                cmin[A[minim][j].varf]=cmin[minim]+A[minim][j].cost;
                prec[A[minim][j].varf]=minim;
            }
    }

}

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