#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],tata[50001],w[50001],k,val;
long int i,n,j,m,last,big,tan;
int x,y,z;
//////////////////////////////////////////////////////////////////////////////
void recon(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)
{big=w[ind2];w[ind2]=w[h];w[h]=big;
 recon(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=n-1;
last=1;
for (i=1;i<n;i++)
	w[i]=i+1;
/////////////////////////////////////////////////////////
while (tan>0)
{
	
	for (k=1;k<=tan;k++)
	{p=a[last];
	while (p!=NULL)
	 {if (p->dest==w[k]){
													 val=d[last]+p->inf;
													 if (val<d[w[k]])
		                                                              d[w[k]]=val;
																	  break;}
	p=p->leg;
	 }
	}
	for (i=tan/2;i>0;i--)
		recon(i);
	last=w[1];
	w[1]=w[tan];
	tan--;
}
for (i=2;i<=n;i++)if (d[i]==50000)fprintf(out,"%c %c",'0',' ');else fprintf(out,"%d %c",d[i],' ');
fclose(in);fclose(out);
return 0;
}