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

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

using namespace std;

struct Node {
	int number,value;
};

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

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

	vector<int> queue;
	
	queue.push_back(startNode);

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

		searched[node] = true;

		for(Node x : graph[node])
		{			
			if ((distanceValues[x.number] == -1) || ((distanceValues[node] + x.value) < distanceValues[x.number])) {
				distanceValues[x.number] = distanceValues[node] + x.value;
			}

			if (searched[x.number] == true)continue;
			queue.push_back(x.number);
		}
	}
}


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

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

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

	Dijktra(startNode,graph,n);

	for (int i = 1; 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