#include <fstream>
#include <vector>
#include <utility>
using namespace std;

#define INF 0x3f3f3f
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int,int> > g[50001];
int T[50001];
int V[50001];
int D[50001];
int m, n;

void Citire();
void Dijkstra(int nod);
void Tati(int nod);
void afis();
int main()
{
	Citire();
	T[1] = 0;
	D[1]  = 0;
	D[0] = INF;
	Dijkstra(1);
	//Tati(n);
	afis();
	fin.close();
	fout.close();
	return 0;
}
void afis(){
	for (int i=2;i<=n;++i)
		fout<<(D[i]==INF?0:D[i]) << " ";
	fout<<endl;
}

void Citire()
{
	int a, b, c;
	
	fin >> n >> m;
	
	for ( ; m; --m)
	{
		fin >> a >> b >> c;
		g[a].push_back(make_pair(b, c));
	}
	
	for ( int i = 1; i <= n; ++i )
		D[i] = INF;
}

void Dijkstra(int nod)
{
	V[nod] = 1;
	for ( vector<pair<int,int> >::iterator it = g[nod].begin(); it != g[nod].end(); ++it )
	{
		T[it->first] = nod;
		D[it->first] = (*it).second;
	}
	int gasit;
	do{
		gasit=0;
		//caut cel mai apropiat varf nevizitat
		int pmin=0;
		for(int i=1;i<=n;++i)
			if(V[i]==0 && D[i]<D[pmin])
				pmin = i;
		if(pmin!=0){
			gasit = 1;
			V[pmin] = 1;
			for ( vector<pair<int,int> >::iterator it = g[pmin].begin(); it != g[pmin].end(); ++it )
				if(V[it->first]==0 && D[it->first] > D[pmin]+it->second)
					D[it->first] = D[pmin] + it->second, T[it->first] = pmin;
		}
	}
	while(gasit);
}

void Tati(int nod)
{
	if ( nod == 1 )
		return;
	fout << nod << ' ';
	Tati(T[nod]);
}