//#include "pch.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

struct Node {
	int number, value;

	bool operator<(const Node& rhs) const
	{
		return value > rhs.value;
	}
};

int MAX = 1 << 30;
vector<Node> graph[50001];
bool searched[50001];
int distanceValues[50001];

void AddNewNode(int x, int y, int cost) {
	Node newNode;
	newNode.number = y;
	newNode.value = cost;
	graph[x].push_back(newNode);
}


void Dijktra(int startNode, int n) {
	
	priority_queue<Node> queue;

	Node newNode;
	newNode.number = startNode;
	newNode.value = 0;

	queue.push(newNode);

	distanceValues[startNode] = 0;

	while (queue.size() > 0) {
		int node = queue.top().number;
		queue.pop();

		searched[node] = true;

		for (Node x : graph[node])
		{
			if (searched[x.number] == true)continue;

			if ((distanceValues[node] + x.value) < distanceValues[x.number]) {
				distanceValues[x.number] = distanceValues[node] + x.value;
			}

			Node node;
			node.number = x.number;
			node.value = distanceValues[x.number];

			queue.push(node);
		}
	}

	for (int i = 1; i <= n; ++i) {
		if (distanceValues[i] == MAX)distanceValues[i] = 0;
	}
}


int main()
{
	int n, m, x, y, cost;

	int startNode = 1;

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

	f >> n >> m;

	for (int i = 1; i <= n; ++i) {
		searched[i] = false;
		distanceValues[i] = MAX;
	}

	while (m--) {
		f >> x >> y >> cost;

		AddNewNode(x, y, cost);
	}

	Dijktra(startNode, n);

	for (int i = 2; i <= n; ++i) {
		g << distanceValues[i] << " ";
	}
}