#include<fstream>
#define nmax 50002
#define mmax 250002
#define inf 2000000000
using namespace std;
struct muchie
{
	long x,y,c;
}G[nmax];
long D[nmax];
long i,x,y,N,M,c,ok;
int main()
{
	   ifstream f("dijkstra.in");
	   ofstream g("dijkstra.out");
	   f>>N>>M;
	   for(i=1;i<=M;i++)
	   {
		   f>>x>>y>>c;
		   G[i].x=x;
		   G[i].y=y;
		   G[i].c=c;
		   if(x==1)
			   D[y]=c;
	   }
	   for(i=2;i<=N;i++)
		   if(D[i]==0)
			   D[i]=inf;
		   do
		   {
			   ok=1;
			   for(i=1;i<=M;i++)
				   if(D[G[i].y]>D[G[i].x]+G[i].c)
				   {
					   D[G[i].y]=D[G[i].x]+G[i].c;
					   ok=0;
				   }
		   }while(!ok);
		   for(i=2;i<=N;i++)
			   if(D[i]!=inf)
				   g<<D[i]<<" ";
			   else
				   g<<" 0 ";
			   return 0;
}