5
5 8 1 3 5
1 2 4
2 3 3
2 4 3
1 5 7

2
10 1
1 2 10

5
1 3 5 1 1
1 2 5
2 3 3
2 4 3
1 5 5

4

2

3