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


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 queue_node{
public:
	int key;
	int dist;
	queue_node(int k) :key(k), dist((std::numeric_limits<int>::max()) / 2-1){};
	queue_node(int k, int d) :key(k), dist(d){};
	queue_node(){};
	struct compare{
		bool operator() (const queue_node& left, const queue_node& right){
			if(left.dist!=right.dist) return left.dist > right.dist;
			else
			{
				return left.key>right.key;
			}
		}
	};
};

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

void list(priority_queue<queue_node,vector<queue_node>,queue_node::compare> q){
	cout << "------------------------" << endl;
	while (!q.empty()){
		
		cout << q.top().key << "-----" << q.top().dist << endl;
		q.pop();
		
	}
	cout << "--------------------------" << endl;
}
//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
int* DIJ(vector<vector<NODE>>&& ad_list){
	priority_queue<queue_node,vector<queue_node>,queue_node::compare> unvisited;

	//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* vis = new int[no_of_vertex];
	for (int i = 0; i < no_of_vertex; i++){ vis[i] = -1; }

	queue_node source(1);
	source.dist = 0;
	unvisited.push(source);

	for (int i = 2; i <= no_of_vertex; i++){
		queue_node aux(i);
		unvisited.push(aux);
	}
	//-------------------	
	
	int n = 0;
	queue_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.top();
		

		unvisited.pop();

		if (vis[curent_node.key - 1] == -1){
			
			for (vector<NODE>::iterator 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]){
						queue_node aux((*it).key, dist[curent_node.key - 1] + (*it).cost);
						unvisited.push(aux);
						dist[(*it).key - 1] = aux.dist;
					}
				}
			}
			vis[curent_node.key - 1] = 1;
			n++;
		}

	}


	return dist;
}


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

	buf.close();
	delete[] data;
}

int main(){

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

	return 0;
}