#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#define MAXIM 100000

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

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