#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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


bool cont[maxN];
queue < int > Q;
vector < int > lista[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].PB(b);
		lista[a].PB(cost);
	}
	
	for (int i = 2; i <= N; ++ i)
		cost[i] = INF;
	
	Q.push(1);
	cont[1] = true;
	
	
	for ( ; Q.size(); )
	{
		int nod = Q.front();
		
		Q.pop();
		
		int minim = INF, poz = 0;
		
		for (unsigned int i = 0; i < lista[nod].size(); i += 2)
		{
			if (cont[lista[nod][i]])
				continue;
			
			int c = cost[nod] + lista[nod][i + 1];
				
			
			if (cost[lista[nod][i]] > c)
				cost[lista[nod][i]] = c;
		}
		
		for (int i = 2; i <= N; ++ i)
		{
			if (cont[i])
				continue;
			
			if (cost[i] < minim)
			{
				minim = cost[i];
				poz = i;
			}
		}
		
		if (poz)
		{
			Q.push (poz);
			cont[poz] = true;
		}
	}
	
	
	for (int i = 2; i <= N; ++ i)
		if (cost[i] == INF)
			g << 0 << " ";
		else
			g << cost[i] << " ";
	
	return 0;
}