#include<fstream>
#define INF 32000
using namespace std;
int d[50010],a[250010][4],i,ok,n,m;
int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=2;i<=n;i++) d[i]=INF;

	for(i=1;i<=m;i++)
 { 
	 f>>a[i][1]>>a[i][2]>>a[i][3];
	 if(a[i][1]==1) d[a[i][2]]=a[i][3];
 }

 while(!ok) 
 { 
	 ok=1;
	 for(i=1;i<=m;i++)
		 if(d[a[i][2]]>d[a[i][1]]+a[i][3])
		 {
			 d[a[i][2]]=d[a[i][1]]+a[i][3];
			 ok=0;
		 }
  }
 
for(i=2;i<=n;i++)
 
 if(d[i]==INF) g<<"0"<<" ";
  else g<<d[i]<<" ";
 
}