Problem Statement

The Kingdom of yukicoder has $N$ cities, numbered from city $1$ to city $N$, and $M$ roads.
The population of city $i\ (1 \le i \le N)$ is $A_i$. Road $i\ (1 \le i \le M)$ bidirectionally connects cities $X_i$ and $Y_i$, and its length is $Z_i$.
Between any $2$ cities of the kingdom, it is possible to travel in both directions by passing through some roads.

King ansain has decided to build power plants in $K$ cities, one after another.
Building the $1$st power plant in city $i$ costs $A_i$.
For the $2$nd and subsequent power plants, building one in city $i$ costs, in addition to $A_i$, the distance from city $i$ to the nearest city with an already built power plant.
Here, the distance between cities $i,j$ is the minimum total length of the roads passed through when traveling from city $i$ to city $j$.

Find the minimum cost required to build power plants in $K$ cities.

Input

$N\ M\ K$
$A_1$ $A_2$ $\dots$ $A_N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_M$ $Y_M$ $Z_M$

Output

Output the minimum cost required to build power plants in $K$ cities. Print a newline at the end.

Sample

3 2 2
3 5 8
1 2 9
2 3 2

15

4 3 3
10000 1 1 1
1 2 1
1 3 2 
1 4 1

8

10 10 1
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
1 2 1
2 3 10
3 4 100
4 5 1000
5 6 10000
6 7 100000
7 8 1000000
8 9 10000000
9 10 100000000
1 10 1000000000

1