#include <stdio.h>
//#define xv w->vf
//#define yc w->c
struct cod
{
int x;
cod *urm;
} *que,*ultim,*next;
struct nod
{
int vf,c;
nod *urm;
};
typedef nod *lista;

lista A[50001];
int C[50001];
bool use[50001];

void add(int x)
{
if (que==NULL)
             {
             next = new cod;
             next->x = x;
             next->urm = NULL;
             que = next;
             ultim = que;
             }
else {
     next = new cod;
     next->x = x;
     next->urm = NULL;
     ultim->urm = next;
     ultim = next;
     }
}

void BF()
{
lista w;
int x,y,c;
while (que!=NULL)
{
w = A[que->x];
c = C[que->x];
use[que->x]=false;
que = que->urm;
while (w!=NULL)
{
x = w->vf; y= w->c;
if (C[x]>c+y || C[x]==0) {C[x]=c+y;if (!use[x]) add(x),use[x]=true;}
w = w->urm;
}
}
}

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 (;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;
}
add(1);
use[1] = true;
BF();
for (i=2;i<=n;i++) fprintf(out,"%d ",C[i]);
}