#include <stdio.h>
#include <limits>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <set>

using namespace std;
//Variable declarations
//---------------------------------------------------
int no_of_vertex, no_of_arches;

typedef struct{
	int key;
	int cost;
}NODE;

typedef struct{
	int* distances;
	int* route;
}RETURN;

//class which will be the elements of the unvisited set
class set_node{
public:
	int key;
	int dist;
	set_node(int k) :key(k), dist((std::numeric_limits<int>::max()) / 2-1){};
	set_node(int k, int d) :key(k), dist(d){};
	set_node(){};
	struct compare{
		bool operator() (const set_node& left, const set_node& right){
			if (left.dist != right.dist) return (left.dist < right.dist);
			else
			{
				return (left.key < right.key);
			}
		}
	};
};

//--------------------------------------------------

//Function that read the data from imput file and return the adjacency list
vector<vector<NODE>> read_data(string file_name){
	vector<vector<NODE>> ad_list;
	ifstream buf;

	buf.open(file_name);

	if (buf.good()){
		buf >> no_of_vertex;
		buf >> no_of_arches;

		ad_list.resize(no_of_vertex);

		for (int i = 0; i < no_of_arches; i++){
			NODE aux;
			int base;
			buf >> base;
			buf >> aux.key;
			buf >> aux.cost;
			ad_list[base - 1].push_back(aux);
		}
	}
	else
	{
		cout << "File was not open properly! ";
	}
	buf.close();
	return ad_list;

}

//The implementation of the Dijsktra algorithm
RETURN* DIJ(vector<vector<NODE>>&& ad_list){
	multiset<set_node, set_node::compare> unvisited;
	vector<NODE>::iterator it;
	//initializing part
	//------------------------
	int* dist = new int[no_of_vertex];
	dist[0] = 0;
	for (int i = 1; i < no_of_vertex; i++){
		dist[i] = std::numeric_limits<int>::max() / 2-1;
	}

	int* prev = new int[no_of_vertex];
	for (int i = 0; i < no_of_vertex; i++){
		prev[i] = 0;
	}

	int* vis = new int[no_of_vertex];
	for (int i = 0; i < no_of_vertex; i++){ vis[i] = -1; }

	set_node source(1);
	source.dist = 0;
	unvisited.insert(source);

	for (int i = 2; i <= no_of_vertex; i++){
		set_node aux(i);
		unvisited.insert(aux);
	}
	//-------------------	

	int n = 0;
	set_node curent_node;//the node that will be extracted from the set in each step, first it will be the source: key 1 for us
	while (n<no_of_vertex){
		
		curent_node = *(unvisited.begin());
		unvisited.erase(unvisited.begin());
		
		//dist[curent_node.key - 1] = curent_node.dist;
		for (it = ad_list[curent_node.key - 1].begin(); it != ad_list[curent_node.key - 1].end(); it++){

			if (vis[(*it).key - 1] == -1){

				if (dist[curent_node.key-1] + (*it).cost < dist[(*it).key - 1]){

					set_node aux((*it).key, dist[(*it).key - 1]);

					unvisited.erase(aux);

					dist[(*it).key - 1] = dist[curent_node.key - 1] + (*it).cost;

					aux.key = (*it).key;
					aux.dist = dist[(*it).key - 1];
					unvisited.insert(aux);

				}
			}
		}
		vis[curent_node.key - 1] = 1;
		n++;
	}


	RETURN *r = new RETURN;
	r->distances = dist;
	r->route = prev;

	return r;
}

//Function which print data to a text file
void write_to_file(string file_name, RETURN* data){
	ofstream buf;
	buf.open(file_name);
	for (int i = 1; i < no_of_vertex; i++){
		if (data->distances[i] == std::numeric_limits<int>::max() / 2 - 1){ buf << 0 << " "; }
		else
		{
			buf << data->distances[i] << " ";
		}
	}
	
	buf.close();
	delete[] data;
}

int main(){

	write_to_file("dijkstra.out", DIJ(read_data("dijkstra.in")));
	return 0;
}