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

#define INFINITE  0x0f0f0f0f
#define UNDEFINED 0x0f1f1f1f
#define START     1

ifstream in ("dijkstra.in");
ofstream out("dijkstra.out");

vector <pair<int, int>> muchii[50001];

int dist[50001];

struct cmp
{
	bool operator() (const int &i, const int &j)
	{
		return dist[i] > dist[j];
	}
};

int main()
{
	int n, m;
	in >> n >> m;

	for (int i = 1; i <= m; ++i)
	{
		int nod1, nod2, cost;
		in >> nod1 >> nod2 >> cost;

		muchii[nod1].push_back(make_pair(nod2, cost));
	}

	priority_queue<int> myQueue;
	set<int> mySet;

	int visited[50001];
	int previous[50001];

	for (int i = 1; i <= n; ++i)
	{
		dist[i]     = INFINITE;
		visited[i]  = 0;
		previous[i] = UNDEFINED;
	}

	dist[START] = 0;
	mySet.insert(0);
	myQueue.push(START);

	while (!myQueue.empty())
	{
		int u = myQueue.top();

		if (u == -1)
			out << "fuck me";

		for (vector<pair<int, int> >::iterator i = muchii[u].begin(); i != muchii[u].end(); ++i)
		{
			int v	 = (*i).first;
			int cost = (*i).second;

			int alt = dist[u] + cost;
			if (alt < dist[v])
			{
				dist[v] = alt;
				previous[v] = u;
				if (!visited[v])
					myQueue.push(v);
			}
		}
	}

	for (int i = 1; i <= n; ++i)
		out << dist[i] << " ";

	return 0;
}