#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define MAXIM 100000

vector <int> graph[100005];
vector <int> graphC[100005];
priority_queue <pair<int, int> > myheap;
int viz[100005];
int dist[100005];

int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	int n, m;
	f >> n >> m;
	int a, b, c;
	for (int i = 1; i <= m; i++)
	{
		f >> a >> b >> c;
		graph[a].push_back(b);
		graphC[a].push_back(c);
	}
	dist[1] = 0;
	myheap.push(make_pair(0, 1));
	for (int i = 2; i <= n; i++)
	{
		dist[i] = MAXIM;
		myheap.push(make_pair(-dist[i], i));
	}
	while (!myheap.empty())
	{
		pair <int, int> best = myheap.top();
		myheap.pop();
		int index = best.second;
		if (viz[index])
			continue;
		viz[index] = 1;
		int lim = graph[index].size();
		for (int i = 0; i < lim; i++)
		{
			int vecin = graph[index][i];
			int cost = graphC[index][i];
			if (dist[index] + cost < dist[vecin])
			{
				dist[vecin] = dist[index] + cost;
				myheap.push(make_pair(-dist[vecin], vecin));
			}
		}
	}
	for (int i = 2; i <= n; i++)
		if (dist[i] == MAXIM)
			g << 0 << " ";
		else
			g << dist[i] << " ";
	return 0;
}