#include <fstream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

vector<int> sol(50001, INT_MAX);

struct cmp
{
	bool operator() (int x, int y)
	{
		return sol[x] > sol[y];
	}
};
int main()
{
	vector<vector<pair<int, int>>> graf;
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	int i, m1, m2, cost;
	int n, m;
	vector<pair<int, int>> v;
	pair<int, int> x;

	in >> n >> m;

	for (i = 0; i <= n ; i++)
	{
		graf.push_back(v);
	}

	for (i = 0; i < m; i++)
	{
		in >> m1 >> m2 >> cost;
		x.first = m2;
		x.second = cost;
		graf[m1].push_back(x);
	}

	//Rezolvare
	
	priority_queue<int, vector<int> ,cmp>  h;
	int nod;

	sol[1] = 0;
	h.push(1);

	while (h.empty() != true)
	{
		nod = h.top();

		for (vector<pair<int, int>>::iterator it = graf[nod].begin(); it != graf[nod].end(); it++)
		{
			if (sol[nod] == INT_MAX)
			{
				break;
			}
			if (sol[it->first] > sol[nod] + it->second)
			{
				sol[it->first] = sol[nod] + it->second;
				h.push(it->first);
			}
		}
		h.pop();
	}

	for (i = 2; i <= n; i++)
	{
		if (sol[i] == INT_MAX)
		{
			out << "0 ";
		}
		else
		{
			out << sol[i] << ' ' ;
		}
	}
	out << '\n';
	return 0;
}