#include <fstream>
#include <vector>
#include <set>
#include <climits>
using namespace std;

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

typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef pair<ull, ull> pulli;

int main()
{
	int N, M;
	in >> N >> M;
	vector<vector<pii>> G(N, vector<pii>());

	for (int i = 0; i < M; i++)
	{
		int u, v, c;
		in >> u >> v >> c;
		u--; v--;
		G[u].push_back({ v, c });
	}
	vector<ull> dist(N, ULLONG_MAX);

	dist[0] = 0;

	set<pulli> pq;
	pq.insert({ 0,0 });
	while (!pq.empty())
	{
		pulli top = *pq.begin();
		int node = top.second;
		int cdist = top.first;
		pq.erase(pq.begin());

		for (auto it = G[node].begin(); it != G[node].end(); it++)
		{
			if (dist[node] + it->second < dist[it->first])
			{
				if (dist[it->first] != LLONG_MAX)
					pq.erase({ dist[it->first], it->first });
				dist[it->first] = dist[node] + it->second;
				pq.insert({ dist[it->first], it->first });
			}
		}
	}
	for (int i = 1; i < N; i++)
	{
		out << (dist[i] == ULLONG_MAX ? 0 : dist[i]) << ' ';
	}
}