#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Flight
{
public:
Flight(unsigned int from, unsigned int to, unsigned int price);
unsigned int from, to, price;
};
Flight::Flight(unsigned int from, unsigned int to, unsigned int price){
this->from = from; this->to = to; this->price = price;
}
// Number of vertices in the graph
unsigned int V = 4;
int minDistance(std::vector<unsigned int> dist, std::vector<bool> sptSet)
{
// Initialize min value
unsigned int min = UINT_MAX, min_index;//INT_MAX, min_index;
for (unsigned int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// A utility function to print the constructed distance array
/*void printSolution(unsigned int dist[], int n)
{
std::cout << "Vertex Distance from Source" << std::endl;//printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}*/
// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
std::vector<unsigned int> dijkstra(vector<vector<unsigned int>> graph/*[V][V]*/, int src)
{
//unsigned int* dist = new unsigned int[V]; // The output array. dist[i] will hold the shortest
std::vector <unsigned int> dist;
// distance from src to i
//bool* sptSet = new bool[V]; // sptSet[i] will true if vertex i is included in shortest
std::vector <bool>sptSet;
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (unsigned int i = 0; i < V; i++){
dist.push_back(UINT_MAX); sptSet.push_back(false);
}//dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (unsigned int count = 0; count < V - 1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (unsigned int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]){
dist[v] = dist[u];
if (v % 2 != 0){//Every other flight is free
dist[v] += graph[u][v];
}
//dist[v] = dist[u] + graph[u][v];
}
}
// print the constructed distance array
//printSolution(dist, V);
//delete[] dist;
//delete[] sptSet;
return dist;
}
/*unsigned int** createMatrix(std::vector <Flight> flights){
//unsigned int* matrix = new unsigned int[3];
//unsigned int** matrix2 = new unsigned int*[flights.size()];
//matrix2
}*/
vector<vector<unsigned int>> createGraph(vector<Flight> flights, unsigned int n){
unsigned int v = n;//flights.size();
vector<vector<unsigned int>> graph;
for (unsigned int i = 0; i < v; i++){
//unsigned int* p = new unsigned int[v];
graph.push_back(vector<unsigned int>());
for (unsigned int z = 0; z < v; z++){
graph.back().push_back(0);
}
}
//Arrange flights by "from"
//For all flights with start point of 1 check the price to dest
for (Flight f : flights){
graph[f.from - 1][f.to - 1] = f.price;
}
return graph;
}
// Driver program to test methods of graph class
int main()
{
/* Let us create the example graph discussed above */
//Price as a distance
unsigned int n = 0;
unsigned int m = 0;
cin >> n;
cin >> m;
V = n;
vector<Flight> flights;
for (unsigned int i = 0; i < m; i++){
unsigned int from, to, price;
cin >> from >> to >> price;
flights.push_back(Flight(from, to, price));
}
//cin >> V;
//vector<Flight> flights;
//flights.push_back(Flight(1, n, 100));
//flights.push_back(Flight(1, 2, 10));
//flights.push_back(Flight(2, n, 10));
vector<vector<unsigned int>> graph = createGraph(flights, n);
//graph[0][1] = 3;
//graph[0][2] = 5;
//graph[1][0] = 2;
//{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
//{ 0, 0, 4, 0, 10, 0, 2, 0, 0 },
//{ 0, 0, 0, 14, 0, 2, 0, 1, 6 },
//{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
//{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
unsigned int price = dijkstra(graph, 0).back();
std::cout << price << std::endl;
return 0;
}