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

using namespace std;

vector<int> graph[5000001];
vector<int> graphCost[5000001];
priority_queue<pair<int, int>> myheap;
int viz[50000001];
int dist[50000001];

#define max_size 999999;

int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	int noduri, muchii, x, y, c;
	fin >> noduri;
	fin >> muchii;
	for (int i = 1; i <= muchii; i++)
	{
		fin >> x >> y >> c;
		graph[x].push_back(y);
		graphCost[x].push_back(c);
	}
	for (int i = 1; i <= noduri; i++)
	{
		if (i == 1)
			dist[i] = 0;
		else dist[i] = max_size;
		myheap.push(make_pair(-dist[i], i));
	}
	while (!myheap.empty())
	{
		pair<int, int>p = myheap.top();
		int index = p.second;
		myheap.pop();
		if (viz[index] == 1);
		else
		{
			viz[index] = 1;
			int lim = graph[index].size();
			for (int k = 0; k < lim; k++)
			{
				int vecin = graph[index][k];
				if (dist[vecin] > (dist[index] + graphCost[index][k]))
				{
					dist[vecin] = dist[index] + graphCost[index][k];
					myheap.push(make_pair(-dist[vecin], vecin));
				}

			}
		}
	}
	for (int i = 2; i <= noduri; i++) {
		if (dist[i] == max_size)
			dist[i] = 0;
		fout << dist[i] << " ";
	}
	return 0;
}