输入：

11

12 24 314 12 12 563 73 13 65 93 5

1 2 342

5 6 92

4 7 23

4 11 1

4 5 55

1 9 30

2 3 37

8 4 84

10 9 12

5 10 10

输出：

37