#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <unordered_map>
#include <fstream>
#include <cstdlib>


using namespace std;

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



int N, M, i,first_node,second_node,weight,A,B,C;
int main()
{
	
	fin >> N >> M;
	vector<int> proccessed_nodes(N + 1,false);
	vector<long long> distances(N + 1, INT_MAX);
	unordered_map<long long, vector<pair<long long, long long>>>nodes(N+1);
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long, long>>> Queue;
	distances[1] = 0;
	Queue.push({ 1,0 });
	for (i = 1; i <= M; i++)
	{
		fin >> A >> B >> C;
		nodes[A].push_back({B,C});
	}
	while (!Queue.empty())
	{
		first_node = Queue.top().first;
		Queue.pop();
		if (proccessed_nodes[first_node])
			continue;
		proccessed_nodes[first_node] = true;
		for (auto it : nodes[first_node])
		{
			second_node = it.first;
			weight = it.second;
			if (distances[first_node] + weight<distances[second_node])
			{
				distances[second_node] = distances[first_node] + weight;
				Queue.push({second_node,distances[second_node]});
			}
		}
	}
	for (i = 2; i <= N; i++)
		fout << distances[i] << " ";
	fin.close();
	fout.close();

	return 0;
}