#include<fstream>
#define INF 32000
using namespace std;
int rasp[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++) rasp[i]=INF;

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

 while(!ok)
 {
	 ok=1;
	 for(i=1;i<=m;i++)
		 if(rasp[a[i][2]]>rasp[a[i][1]]+a[i][3])
		 {
			 rasp[a[i][2]]=rasp[a[i][1]]+a[i][3];
			 ok=0;
		 }
  }

for(i=2;i<=n;i++)

 if(rasp[i]==INF) g<<"0"<<" ";
  else g<<rasp[i]<<" ";

}