#include <fstream>
#include <iostream>
#include <map>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

map <unsigned int, map<unsigned int,unsigned int> > v;
unsigned int 	n;
const int     INF=9999999;
unsigned int 	Dist[250000];
bool				 	Viz[250000];
void 					citire();
unsigned int	det_min_neviz();
void          dijkstra(int nod);
inline int    min(int a,int b){return a<b?a:b;}
int main()
{
	citire();
	Viz[1]=true;
	memset(Dist,0xff,(n+1)*sizeof(int));
	for(int i=1; i<=n; i++)
		if(v[1][i])
			Dist[i]=v[1][i];


	int start=det_min_neviz();

	dijkstra(start);

	for(int i=2; i<=n; i++)
		if(Dist[i]==INF)
			g<<0<<" ";
		else
			g<<Dist[i]<<" ";
	return 0;
}

void dijkstra(int nod)
{
	Viz[nod]=true;

	for(int i=2; i<=n; i++)
	{
		int mx=v[nod][i];
		if(mx==0)
			mx=INF;
		Dist[i]=min(Dist[i],Dist[nod]+mx);
	}

	int start=det_min_neviz();
	if(start)
		dijkstra(start);
}

unsigned int det_min_neviz()
{
	int min=INF,
			min_poz=0;

	for(int i=1; i<=n; i++)
	{

		if(Viz[i]==false && Dist[i]<min)
		{
			min_poz=i;
			min=Dist[i];
		}
	}
	return min_poz;
}

void citire()
{
	unsigned int muchii;
	f>>n;
	f>>muchii;

	unsigned int a,b,cost;
	while(f>>a>>b)
	{
		f>>cost;
		v[a][b]=cost;
	}

}