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

//#include "pch.h"
#include <iostream>
#include <fstream>
#include <deque>
#include <list>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define INF 0x3f3f3f3f 
class Graph {
private:
	int nVertices, nEdges;
	list< pair<int, int> > * adjacencyList;
public:
	
	void insertVertices() {
		
		int nVertices, nEdges;
		fin >> nVertices >> nEdges;
		adjacencyList = new list< pair<int, int> >[nVertices];
		this->nVertices = nVertices;
		this->nEdges = nEdges;
		int x, y, w;
		for (int i = 1; i <= nEdges; ++i) {
			fin >> x >> y >> w;
			adjacencyList[x].push_back(make_pair(y, w));
		}
	}
	void dijkstra(int start){
		deque<bool> discovered;
		deque<int> cost;
		for (int i = 1; i <= nVertices + 1; ++i) {
			discovered.push_back(false);
			cost.push_back(INF);
		}
		cost[start] = 0;
		int v = start;
		while (discovered[v] == false) {
			discovered[v] = true;
			list< pair<int, int> >::iterator i = adjacencyList[v].begin();
			while (i != adjacencyList[v].end()) {
				if (cost[i->first] > (cost[v] + i->second)) {
					cost[i->first] = cost[v] + i->second;
				}
				++i;
			}
			v = 1;
			int dist = INF;
			for (int i = 0; i < nVertices; ++i) 
				if (discovered[i] == false && (dist > cost[i])) {
					dist = cost[i];
					v = i;
					
				}
			
		}
		for (int i = 2; i <= nVertices; ++i) {
			fout << cost[i] << " ";
		}
	}
};
int main()
{
	Graph g;
	g.insertVertices();
	g.dijkstra(1);
}

// 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