#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
using namespace std;

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

int N, M;
map<int, vector<pair<int, int>>> G;
map<int, int> dist;

const int INF = 1 << 30;

void Read()
{
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int x, y, c;
		fin >> x >> y >> c;
		G[x].push_back({ y, c });
	}
}

void Write()
{
	for (int i = 2; i <= N; i++)
		if (dist[i] == INF)
			fout << "0 ";
		else
			fout << dist[i] << " ";
}

void Dijkstra(int source)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;

	for (int i = 1; i <= N; i++)
		dist[i] = INF;

	dist[source] = 0;
	queue.push({ dist[source], source });
	while (!queue.empty())
	{
		int node = queue.top().second;
		int d = queue.top().first;
		queue.pop();

		if (dist[node] != d)
			continue;

		for (auto child : G[node])
		{
			int to = child.first;
			int cost = child.second;
			if (dist[to] > dist[node] + cost)
			{
				dist[to] = dist[node] + cost;
				queue.push({ dist[to], to });
			}
		}
	}
}

int main()
{
	Read();
	Dijkstra(1);
	Write();

	return 0;
}