Description

给定n个点，m条双向边的图。其中有k个点是重要的。每条边都有一定的长度。

现在要你选定一些边来构成一个图，要使得k个重要的点相互连通，求边的长度和的最小值。

Format

Input

共m+2行

第1行：n,k,m，n个点，k个重要的点，m条边；

第2行共K个点

第3至第m+2行,每行包括3个数字,a,b,c,表示有一条从a到b长度为c的双向路径

k<=5

n<=10^5

1<=m<=2*(10^5)

Output

共1行，即最小长度和

Samples

4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8

11