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

using namespace std;

#define INFINITY INT32_MAX-100
#define IPair pair<int,int>

int N, M;

void solve(vector<int>& distances, vector<bool>& visited, vector<vector<IPair>>& links)
{
	priority_queue<IPair, vector<IPair>, greater<IPair>> pq;
	pq.push(make_pair(0, 0));
	distances[0] = 0;

	while (!pq.empty())
	{
		IPair nod = pq.top();
		pq.pop();
		int source = nod.second;
		int total = nod.first;

		if (visited[source]) continue;
		visited[source] = true;

		for (auto it = links[source].begin(); it != links[source].end(); it++)
		{
			nod = (*it);
			int destination = nod.first;
			int weight = nod.second;

			if (distances[destination] > distances[source] + weight)
			{
				distances[destination] = distances[source] + weight;
				pq.push(make_pair(distances[destination], destination));
			}
		}
	}
}

int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	// Program
	f >> N >> M;
	vector<int> dist(N,INFINITY);
	vector<bool> visited(N);
	vector<vector<IPair>> links(M);
	visited[0] = false;
	
	for (int i = 0; i < M; i++)
	{
		int origin, destination, weight;
		f >> origin;
		f >> destination;
		f >> weight;
		links[origin-1].push_back(make_pair(destination-1, weight));
	}

	solve(dist,visited,links);

	for (int i = 1; i < N; i++)
	{
		if (dist[i] == INFINITY)
		{
			g << "0 ";
		}
		else
		{
			g << dist[i] << " ";
		}
	}

	// Exit
	f.close();
	g.close();
	return 0;
}