/*

^^^TEST^^^
4
1 2 1 5
0 1
0 2
1 2
1 3
2
-----
12.0
$$$TEST$$$

^^^TEST^^^
3
1 2 5
0 1
0 2
1 2
3
-----
15.0
$$$TEST$$$

^^^TEST^^^
4
1 2 5 8
0 1
1 2
2 3
3 0
3
-----
30.0
$$$TEST$$$

^^^TEST^^^
5
1 2 5 8 10
0 1
1 2
2 3
3 0
3 4
3.14
-----
50.2
$$$TEST$$$

^^^TEST^^^
5
1 20 5 8 10
0 1
1 2
2 3
3 0
3 4
3.14
-----
94.2
$$$TEST$$$


^^^TEST^^^
5
1 3 5 8 10
0 1
0 4
1 2
1 3
2 3
3.14
-----
56.5
$$$TEST$$$

^^^TEST^^^
6
1 3 5 8 10 7
0 1
0 4
1 2
1 3
2 3
3 5
0.66
-----
14.5
$$$TEST$$$

^^^TEST^^^
5
1 2 3 4 5 
0 1 
2 3 
2 4 
0 2 
3 4 
9.0
-----
63.0
$$$TEST$$$


^^^TEST^^^
8
3 5 4 1 4 4 3 4
0 1
1 2
2 3
3 0
5 0
6 5
1 7
1 8
1.11111
-----
15.6
$$$TEST$$$

^^^TEST^^^
8
1 1 1 1 1 1 1 1
0 1
1 2
2 3
3 0
5 0
6 5
0 7
0 8
1.11111
-----
4.4
$$$TEST$$$

^^^TEST^^^
8
3 3 2 2 2 4 5 4
0 1
1 2
2 3
3 0
5 0
6 5
0 7
0 8
1.11111
-----
15.6
$$$TEST$$$

*/