Wakanda Forever

We all know that Thanos has erased half of the population of the universe. Earth’s population was also decreased from 7 billion to 3.5 billion.

In Wakanda there are n cities (numbered 1 to $n$) connected by m bidirectional roads.

As T’Challa was disintegrated by the Thanos snap, M’Baku is the new king of Wakanda. M’Baku wants to close some of the roads of Wakanda because the population of some cities were erased completely and some roads are unnecessary.

As you are M’Baku‘s friend, he asked you to help him to minimize the number of roads necessary so that all cities with people are connected and the total length of all active roads will be minimized.

Note that, it is possible that by closing some roads, Wakanda may not be connected anymore. In that case, M’Baku will need to create some new roads each having length $d$.

If a city doesn’t have any people left on it, all roads connected to it should be closed.

Input

The first line of the input contains three integers, $n$, $m$ and $d$ ($2 ≤ n ≤ 10^5$, $n-1 ≤ m ≤ 3 * 10^5$, $1 ≤ d ≤ 100$), the number of cities currently in Wakanda, the number of roads and the lengths of new roads.

The second line contains n integers, denoting number of people $a[i]$ ($0 ≤ a[i] ≤ 100$) in city i after the disintegration.

The next m lines each contain three integers, $u$, $v$ and $w$ ($1 ≤ u, v ≤ n$, $1 ≤ w ≤ 100$), the road end-points and lengths.

Output

Print the total length of all active roads after you help M’Baku.

Sample

Input	Output
5 6 100 100 100 5 0 10 1 2 3 1 4 1 1 3 3 3 4 1 2 4 5 4 5 1	106