There are n construction sites in a town. We want to supply water for all the construction sites by building wells and laying pipes. For each site i, we can either build a well inside it directly with cost wells[i-1], or pipe in water from another well to it. The costs to lay pipes between sites are given by the 2d array cost, where each row of cost contains 3 numbers ai,bi and wi where wi is the cost to connect ai to bi. connections are bidirectional. Return the minimum total cost to supply water to all the construction sites.
Input Format
First line contains two integers V and E denoting number of houses and number of pipelines respectively. Second line contains n integer denoting cost to dig well at ith house. Each of next E lines contain 3 numbers ui and vi and c denoting a pipeline between u and v with cost c to build.
Output Format
Return the minimum total cost to supply water to all the construction sites.
Constraints
1 <= n <= 10^4 wells.length == n 0 <= wells[i] <= 10^5 1 <= cost.length <= 10^4 cost[i].length == 3
Example
Input
3 2 1 2 2 1 2 1 2 3 1
Output
3