#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){};
	queue_node(int k, int d) :key(k), dist(d){};
	queue_node(){};
	struct compare{
		bool operator() (const queue_node& left, const queue_node& right){
			return left.dist > right.dist;
		}
	};
};

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

//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){
	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;
	}

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

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


	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 (!unvisited.empty()){
		curent_node = unvisited.top();
		unvisited.pop();
		if (vis[curent_node.key - 1] == -1){
			vis[curent_node.key - 1] = 1;
			dist[curent_node.key - 1] = curent_node.dist;


			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 (curent_node.dist + (*it).cost < dist[(*it).key - 1]){
						queue_node aux((*it).key, curent_node.dist + (*it).cost);
						unvisited.push(aux);
						dist[(*it).key - 1] = curent_node.dist + (*it).cost;
						prev[(*it).key - 1] = curent_node.key;
					}
				}
			}
		}
		for (int i = 0; i < no_of_vertex; i++){
			cout << dist[i] << "  ";
		}
		cout << endl;
		cout << "--------------------" << endl;
	}


	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++){
		buf << data->distances[i] << " ";
	}
	buf << endl;
	for (int i = 1; i < no_of_vertex; i++){
		buf << data->route[i] << " ";
	}
	buf.close();
	delete[] data;
}

int main(){

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