#include <stdio.h>
#define father(x) ((x)/2)
#define lson(x) ((x)*2)
#define rson(x) ((x)*2+1)

struct NOD
    { int inf,cost;
      struct NOD *urm;};
typedef struct NOD *Lista;
Lista A[50000],H[200010];
int cost[50000],l;

void percolate(int x)
{
    Lista key = H[x];
    while (x>1 && key->cost<H[father(x)]->cost)
    { H[x] = H[father(x)];
        x  = father(x);
    }
    H[x] = key;
}
void shift(int N,int x)
{
int son;
Lista P;
    do{
        son = 0;
        if (lson(x)<=N) {
            son = lson(x);
            if (rson(x)<=N && H[lson(x)]->cost>H[rson(x)]->cost) son = rson(x);
            if (H[son]->cost>H[x]->cost) son=0;
        }
        if (son) {
                P = H[son];
                H[son] = H[x];
                H[x] = P;
                x = son;
                }
        }while(son);
}

void add(Lista P)
{
if (!l) {l=1;H[l]=P;}
else {
        l++;
        H[l]=P;
        percolate(l);
     }
}

void remove()
{
    H[1]=H[l];
    l--;
    shift(l,1);
}




int main()
{
    FILE *in=fopen("dijkstra.in","r");
    int m,n;
    fscanf(in,"%d%d",&n,&m);

    int i,x;
    Lista urm;

    for (i=2;i<=n;i++) cost[i]=50000000;

    for (i=0;i<m;i++)
    {
        urm = new NOD;
        fscanf(in,"%d%d%d",&x,&urm->inf,&urm->cost);
        urm->urm = A[x];
        A[x] = urm;
    }


    while (A[1]!=NULL)
    {
        cost[A[1]->inf] = A[1]->cost;
        add(A[1]);
        A[1] = A[1]->urm;
    }

        int c;
    Lista Q;
    while (l)
{
    c = H[1]->inf;
    Q = A[c];
    remove();
    while (Q!=NULL) {
        if ((cost[Q->inf]>cost[c]+Q->cost)) { cost[Q->inf] = cost[c]+Q->cost;
                                                add(Q);
                                                }
    Q = Q->urm;
    }
}


    FILE *out=fopen("dijkstra.out","w");
    for (i=2;i<=n;i++) if (cost[i]==50000000) fprintf(out,"0 ");
                        else fprintf(out,"%d ",cost[i]);
    fclose(in);fclose(out);
}