#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define maxN 50005
#define INF (1 << 30)

vector < pair <int, int> > lista[maxN];
bool cont[maxN];
int cost[maxN], N, M;


int main()
{
	ifstream f( "dijkstra.in" );
	ofstream g( "dijkstra.out" );
	
	f >> N >> M;
	
	for (int i = 1; i <= M; ++ i)
	{
		int a, b, cost;
		
		f >> a >> b >> cost;
		
		lista[a] . push_back( make_pair (b, cost) );
	}
	
	for (int i = 2; i <= N; ++ i)
		cost[i] = INF;
	
	int nod = 1;
	cost[1] = 0;
	cont[1] = true;
	
	
	for (int i = 1; i <= N; ++ i)
	{
		int poz = 0, minim = INF;
		
		for (int j = 0; j < lista[nod].size(); ++ j)
		{
			if ( cont[lista[nod][j].first] )
				continue;
			
			int c = cost[nod] + lista[nod][j].second;
			
			
			
			if (c < cost[lista[nod][j].first] )
				cost[lista[nod][j].first] = c;
		}
		
		for (int j = 2; j <= N; ++ j)
		{
			if (cont[j])
				continue;
			
			if (cost[j] < minim)
			{
				minim = cost[j];
				poz = j;
			}
		}
		
		if (poz)
		{
			nod = poz;
			cont[poz] = true;
		}
	}
	
	for (int i = 2; i <= N; ++ i)
		if (cost[i] == INF)
			g << 0 << " ";
		else
			g << cost[i] << " ";
	
		
	f.close();
	g.close();
	
	return 0;
}