#include <cstdio>
using namespace std;
FILE *in=  fopen("dijkstra.in","r");
FILE *out=fopen("dijkstra.out","w");
struct nod{int dest;int inf;nod *leg;};

nod *a[50000],*p;
int d[50001],poz[50001],w[50001],k,val;
long int i,n,j,m,last,big,tan;
int x,y,z;
//////////////////////////////////////////////////////////////////////////////
void up(int h)
{int ind=h/2;int ind2=0;

int aux=w[h];


	if (d[aux]<d[ w[ind] ]){aux=w[ind];ind2=ind;}

if (ind2!=0)
{poz[aux]=ind2;poz[w[ind]]=h;
	big=w[ind2];w[ind2]=w[h];w[h]=big;
 up(ind2);
}
}
///////////////////////////////////////////////////////////////
void dow(int h)
{int ind=h*2;int ind2=0;

int aux=w[h];

for (int j=ind;j<ind+2;j++)
	if (j<=tan)
	if (d[aux]>d[ w[j] ]){aux=w[j];ind2=j;}
if (ind2!=0)
{poz[aux]=ind2;poz[w[ind2]]=h;
	big=w[ind2];w[ind2]=w[h];w[h]=big;
 dow(ind2);
}
}
////////////////////////////////////////////////////////////////////
int main()
{fscanf(in,"%ld %ld",&n,&m);

for (i=1;i<=n;i++){a[i]=NULL;d[i]=50000;}
d[1]=0;

for (i=1;i<=m;i++)
{fscanf(in,"%d %d %d",&x,&y,&z);
p=new(nod);
p->dest=y;
p->inf=z;
p->leg=a[x];
a[x]=p;

}

tan=0;
last=1;

/////////////////////////////////////////////////////////
do
{
 
	p=a[last];
 while (p!=NULL)
 {	val=d[last]+p->inf;
    i=p->dest; 
	if (val<d[i]){d[i]=val;
						if (poz[i]==0){tan++;
												poz[i]=tan;
	                                              w[tan]=i;
						                              up(tan);}
						else {up(poz[i]);dow(poz[i]);}
	}
	p=p->leg;
 }
last=w[1];
w[1]=w[tan];
if (tan>0)tan--;
dow(1);
p=a[last];

	
}
while ((p!=NULL)or(tan>0));
	
for (i=2;i<=n;i++)
	if (d[i]==50000)fprintf(out,"%c ",'0');
       else fprintf(out,"%d ",d[i]);
	
fclose(in);fclose(out); 
return 0;
}