int Graph::minDistance(int dist[], bool sptSet[])
{
   // Initialize min value
   int min = INT_MAX, min_index;

   for (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
int Graph::printSolution(int dist[], int n)
{
   cout<<endl<<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
void Graph::dijkstra(Graph& G, int src)
{

     int dist[V];
     bool sptSet[V];
     for (int i = 0; i < V; i++){
        dist[i] = INT_MAX, sptSet[i] = false;
     }
     dist[src] = 0;
     for(int i=0;i<V;i++){
        int u=minDistance(dist,sptSet);
        sptSet[u]=true;//visited
        for(int v=0;v<V;v++){
            for(auto e:edge[v]) dist[v+1]=e.second+dist[v];

        }
     }
    printSolution(dist,V);
}