#include <fstream>
#include <vector>
#include <queue>
#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;

class Comparator
{
	public:
		bool operator()(pair<ull, int> a, pair<ull, int> b) const
		{
			return a.first > b.first;
		}
};
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;

	priority_queue<pair<ull,int>, vector<pulli>, Comparator> pq;
	pq.push({ 0,0 });
	vector<bool> visited(N, false);
	while (!pq.empty())
	{
		pulli top = pq.top();
		int node = top.second;
		int cdist = top.first;
		pq.pop();
		if (!visited[node])
		{
			visited[node] = true;
			for (auto it = G[node].begin(); it != G[node].end(); it++)
			{
				if (!visited[it->first] && dist[node] + it->second < dist[it->first])
				{
					dist[it->first] = dist[node] + it->second;
					pq.push({ dist[it->first], it->first});
				}
			}
		}
	}
	for (int i = 1; i < N; i++)
	{
		out << (dist[i] == LLONG_MAX ? 0 : dist[i]) << ' ';
	}
}