You are asked to Create a C$++$ program that uses Graphs to find the shortest paths between vertices in graphs. We will use the classic Dijkstra$$s algorithm to find the shortest distance from a starting vertex to every other vertex in a graph. We will use this to find the distance between every pair of vertices in a graph and display the results. As an example, consider a weighted graph: This graph can be represented in an adjacency matrix as:

$--4----------8--$

$4--8--------11--$

$--8--7--4----2$

$----7--914------$

$------9--10------$

$----41410--2----$

$----------2--16$

$811--------1--7$

$----2------67--$

Input files

$-$ The input files contain several lines with integer values, separated by spaces as needed. All input files are well formed with valid values. There is no need for exception handling on the inputs and all files follow the same format.

$-$ The first line provides the number of vertices in the graph. This value will always be positive and there will always be multiple rows containing the edges in the graph. There will never be a degenerate graph that is empty or contains no edges.

$-$ The next lines in the file contain the values for each edge in the graph. These lines contain the from$-$vertex number, the to$-$vertex number and the weight of the edge. These will be positive integer values, well always appear in groups of three, and each of the numbers is separated by a space.

For example, the input$1.$txt contains:

$9$

$014$

$078$

$104$

$128$

$1711$

$218$

$237$

$254$

$282$

$327$

$349$

$3514$

$439$

$4510$

$524$

$5314$

$5410$

$562$

$652$

$671$

$686$

$708$

$7111$

$761$

$787$

$822$

$866$

$877$

This corresponds to the graph shown above. We can compute the shortest distance from any vertex to any other vertex. Suppose we pick vertex $0$ as the starting point, the distance to every other vertex is then:

$04121921119814$

Continuing, we can compute the shortest distance to all vertices starting from vertex $1,2,$ and so on$.$

Output files

$-$ Output the minimum distance through the graph to each other vertex, starting from each vertex in order. Output the results for each starting vertex, one per line.

$-$ Output the minimum distance one each line with $2$ spaces allowed for each number and a space before and after each value.

For example, the ans$1.$txt contains:

$04121921119814$

$408152212121110$

$12807144672$

$19157091113149$

$2122149010121316$

$1112411100236$

$912613122016$

$811714133107$

$141029166670$