#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <queue>
#include <cmath>
#include <string>
#include <set>
using namespace std;

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

// DIJSKTRA with MIN-HEAP using SET

#define INF 20000000
const int NMAX = 50015;

vector<pair<int, int>> adjList[NMAX];// vector <adjNode,edgeCost>
int dist[NMAX];
int n, m;

void read()
{
	in >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y, c;
		in >> x >> y >> c;
		adjList[x].push_back(make_pair(y, c));
	}
}

void Dijsktra(int startNode)
{
	dist[startNode] = 0;
	set<pair<int, int>> heap;
	heap.insert(make_pair(startNode, 0)); // <node,cost>

	while (!heap.empty())
	{
		int node = heap.begin()->first;
		heap.erase(heap.begin());

		for (const auto& edge : adjList[node])
		{
			int nextNode = edge.first;
			int cost = edge.second;
			if (dist[nextNode] > dist[node] + cost)
			{
				if (dist[nextNode] != INF) //already exists(visited)
				{
					heap.erase(heap.find({ nextNode, dist[nextNode] }));
					// we remove the element
					// in order to update it
				}
				dist[nextNode] = dist[node] + cost;
				heap.insert({ nextNode, dist[nextNode] });
			}
		}

	}
}

void print()
{
	for (int i = 2; i <= n; i++)
	{
		if (dist[i] == INF)//unvisited 
			dist[i] = 0;
		out << dist[i] << ' ';
	}
}

int main()
{
	read();
	for (int i = 0; i <= n + 1; i++)
		dist[i] = INF;
	Dijsktra(1);
	print();
}