# UVa 10600

## Summary

Given a Graph, find the Minimum Spanning Tree and the second Minimum Spanning Tree.

## Explanation

Find the Minimum Spanning Tree. (${\displaystyle O(V^{2})}$ implementation is fine.) Since the Minimum Spanning Tree algorithm is a Greedy algorithm, one of the second Minimum Spanning Tree should have nearly the same structure, if we were not so greedy on the edges. Note that in the Minimum Spanning Tree, there are V-1edges. We can bruteforce this by removing the edges of the Minimum Spanning Tree one at a time, and calculating the resultant Minimum Spanning Tree. The one with the minimum cost would be the second Minimum Spanning Tree. The total complexity is ${\displaystyle O(V^{3})}$.

```3
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10
4 4
1 4 5
1 2 2
2 3 3
1 3 4
```

## Output

```110 121
37 37
10 11
```