Sample 1

Input

5 6 3
1
2
3
1 2 1
1 5 2
3 2 3
3 4 5
4 2 7
4 5 10

Output

12

【样例解释】
FJ 在 5 号城镇建立农场。他每天的行走路线为 5-1-2-3-2-1-5，路线长度为
12

Limitation

1s, 128MiB for each test case.