Nguồn

Ví dụ:

Input

4
1 3 4 2

Output

4
8
14
18

Nguồn

Ví dụ:

Input

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

Output

5

Ví dụ 2:

Input

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

Output

7

Nguồn