// InfoArenaDijkstra.cpp : This file contains the 'main' function. Program execution begins and ends there.
//


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

using namespace std;

struct Node {
	int number,value;
};

int MAX = 1 << 30;

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

bool searched[50001];
int distanceValues[50001];

struct Comparison {
	bool operator()(const pair<int, int> left, const pair<int, int> right) const {
		return left.first < right.first;
		}
};

void Dijktra(int startNode, vector<Node> graph[50001],int n) {

	vector<pair<int,int>> queue;
	
	queue.push_back(make_pair(0,startNode));

	make_heap(queue.begin(), queue.end(), Comparison());

	distanceValues[startNode] = 0;
	
	while (queue.size() > 0) {
		int node = queue.back().second;
		queue.pop_back();

		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;
			}

			queue.push_back(make_pair(distanceValues[x.number],x.number));
			push_heap(queue.begin(), queue.end());
		}
	}

	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;
	}
	vector<Node> graph[50001];

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

		AddNewNode(graph, x, y, cost);
	}

	Dijktra(startNode,graph,n);

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

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file