$N$개의 도시가 있다. 하지만 현재 교통 시설이 지어지지 않아, 도시 사이를 오갈 수 없다.

도로 건설 계획이 $M$개 있다. $i$번째 계획을 선택하면 도시 $u_i$와 도시 $v_i$를 잇는 양방향 도로를 $w_i$의 비용으로 건설할 수 있다.

또한, 각 도시에는 공항을 지을 수 있다. 도시 $i$에 공항을 짓는 비용은 $A_i$이다. 공항이 지어진 두 도시 사이는 비행기를 이용하여 자유롭게 이동할 수 있다.

도로 건설과 공항 건설 중 일부를 선택하여, 어떤 두 도시를 골라도 도로와 비행기를 이용하여 한 도시에서 다른 도시로 이동할 수 있게 하려고 한다. 이때, 조건을 만족시키기 위해 필요한 총 건설 비용의 최솟값을 구하여라.

입력

첫째 줄에 도시의 수 $N$과 도로 건설 계획의 수 $M$이 공백을 사이에 두고 주어진다.

$$1 \le N \le 10^5,\quad 0 \le M \le 10^5$$

다음 $M$개의 줄에 걸쳐 각 계획의 정보가 주어진다. 이 중 $i$번째 줄에는 세 정수 $u_i$, $v_i$, $w_i$가 공백을 사이에 두고 주어진다. 이는 도시 $u_i$와 도시 $v_i$를 잇는 양방향 도로를 $w_i$의 비용으로 건설할 수 있음을 의미한다.

$$1 \le u_i,v_i \le N,\quad u_i \ne v_i,\quad 1 \le w_i \le 10^9$$

마지막 줄에 $N$개의 정수 $A_1,A_2,\ldots,A_N$이 공백을 사이에 두고 주어진다. $A_i$는 도시 $i$에 공항을 짓는 비용이다.

$$1 \le A_i \le 10^9$$

여러 개의 도로 건설 계획이 같은 도시 쌍 사이를 이을 수 있다.

출력

어떤 두 도시 사이도 이동 가능하도록 만드는 데 필요한 총 건설 비용의 최솟값을 출력한다.

입출력 예시

예제 1

입력

4 2
1 2 4
3 4 4
3 10 2 10

출력

13

예제 2

입력

3 3
1 2 1
2 3 1
1 3 10
100 100 100

출력

2

노트

첫 번째 예제에서는 도시 $1$과 도시 $2$를 잇는 도로, 도시 $3$과 도시 $4$를 잇는 도로를 건설하고, 도시 $1$과 도시 $3$에 공항을 짓는 것이 최적이다. 총 비용은 $4+4+3+2=13$이다.

두 번째 예제에서는 공항을 짓지 않고 도시 $1$과 도시 $2$, 도시 $2$와 도시 $3$을 잇는 도로를 건설하는 것이 최적이다. 총 비용은 $1+1=2$이다.