#include<fstream>
#include<vector>

#define dmax 50001
#define inf 999999

using namespace std;

int n,m,inc,sfc,d[dmax],q[500000],uz[dmax];

vector<int> a[dmax];
vector<int> cost[dmax];
/*vector<int> q;*/

int main()
{
 int i,j,x,y,c,elem;
	
 /*ifstream fin("dijkstra.in");*/ 
 FILE *fin;
 fin = fopen("dijkstra.in","r");
 /*fin>>n>>m;*/
 fscanf(fin,"%d %d",&n, &m);
 for (i=1; i<=m; i++)
	 {
	  /*fin>>x>>y>>c;*/
      fscanf(fin,"%d %d %d",&x, &y, &c);
	  a[x].push_back(y);
	  cost[x].push_back(c);
	 }
 
 inc=0; sfc=1;
 /*q.push_back(1); q.push_back(1);*/
 q[1]=1;
 
 for (i=2; i<=n; i++)
	 d[i]=inf;
  
 while (inc<=sfc)
	 {
	  inc++; elem=q[inc];
	  
	  for (i=0; i<a[elem].size(); i++)
			  if (d[a[elem][i]] > d[elem] + cost[elem][i])
				 {
				  d[a[elem][i]]= d[elem] + cost[elem][i];
				  sfc++; 
				  /*q.push_back(a[elem][i]);*/
				  q[sfc]=a[elem][i];
				 }
	 }
 
 /*ofstream fout("dijkstra.out");*/
 FILE *fout;
 fout = fopen("dijkstra.out","w");
 
 for (i=2; i<=n; i++)
	 if (d[i]!=inf)
		 /*fout<<d[i]<<" ";*/
		 fprintf(fout,"%d ",d[i]); else
		 fprintf(fout,"0 ");
	
 fclose(fin);
 fclose(fout);
 
 return 0;
}