#include <stdio.h>

struct nod
{
int vf,c;
nod *urm;
};
typedef nod *lista;

lista A[50001],que,ultim;
int C[50001];

void add(int x,int c)
{
lista urm;
if (que==NULL)
             {
             urm = new nod;
             urm->vf = x;
             urm->c = c;
             urm->urm = NULL;
             que = urm;
             ultim = que;
             }
else {
     urm = new nod;
     urm->vf = x;
     urm->c = c;
     urm->urm = NULL;
     ultim->urm = urm;
     ultim = urm;
     }
}

void BF(int p,int c)
{
lista w;
w = A[p];
while (w!=NULL)
{
if (C[w->vf]==-1 || C[w->vf]>c+w->c) C[w->vf]=c+w->c,add(w->vf,c+w->c);
w = w->urm;
}
if (que!=NULL) que = que->urm,BF(que->vf,que->c);
}

int main()
{
FILE *in = fopen("dijkstra.in","r");
FILE *out = fopen("dijkstra.out","w");

int n,i,m,x,y,c;
lista urm;
fscanf(in,"%d%d",&n,&m);
for (i=1;i<=n;i++) C[i]=-1;

for (;m;m--)
{
fscanf(in,"%d%d%d",&x,&y,&c);
urm = new nod;
urm->vf = y;
urm->c = c;
urm->urm = A[x];
A[x] = urm;
}

int s = 1;
C[s] = 0;
add(s,0);

BF(que->vf,que->c);
for (i=2;i<=n;i++) fprintf(out,"%d ",C[i]);

}