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


int n,muchii;
int v[1000][1000];
int Dist[1000];
int	Viz[1000];
const int INF=999999;
void citire();
int  det_min_neviz();
void debug();
void Dijkstra(int nod);
inline int min(int a,int b){return (a<b?a:b);}
int main()
{
	citire();
	for(int i=1; i<=n; i++)
		Dist[i]=v[1][i];

	Viz[1]=true;

	int start=det_min_neviz();
	Dijkstra(start);
	//debug();

	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=1; i<=n; i++)
		Dist[i]=min(Dist[i],Dist[nod]+v[nod][i]);

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

int det_min_neviz()
{
	int dmin=INF,
			min_poz=0;
	for(int i=2; i<=n; i++)
		if(Viz[i]==false && Dist[i]<dmin)
		{
			dmin=Dist[i];
			min_poz=i;
		}
	return min_poz;
}
void citire()
{
	f>>n>>muchii;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			v[i][j]=INF;

	int a,b;
	while(f>>a>>b)
		f>>v[a][b];
}
void debug()
{
	for(int i=1; i<=n; i++)
	{
		cout<<endl;
		for(int j=1; j<=n; j++)
		{
			cout.width(6);cout<<v[i][j]<<" ";
		}
	}

	cout<<endl<<endl;
	for(int i=1; i<=n; i++)
		cout<<Dist[i]<<" ";
	cout<<endl;
	for(int i=1; i<=n; i++)
		cout<<Viz[i]<<" ";
}