모든 길은 요코하마로 통하는가?

제한 시간: 3000 ms. 메모리 제한: 2048 MB.

"Omnes viae Romam ducunt"는 "모든 길은 로마로 통한다"라는 뜻의 오래된 라틴어 속담이다. 한 나라의 모든 지역에서 수도로 갈 수 있는 것은 지금도 바람직하다.

카나가와 왕국에는 수도 요코하마를 포함해 여러 도시가 있다. 왕국의 교통부는 이 도시들을 모두 잇는 고속도로망을 건설할 계획이다.

후보 고속도로 구간은 여러 개이며, 각 구간은 두 도시를 직접 잇는다. 고속도로망은 후보 구간 중에서 골라 만든 구간의 집합이다. 고속도로망은 다음 조건을 만족해야 한다.

• 모든 도시는 고속도로 구간을 통해 직접 또는 간접적으로 연결되어야 한다.
• 예산을 아끼기 위해 구간 수는 최소여야 한다. 즉 고속도로망은 중복되지 않아야 하며, 임의의 두 도시를 잇는 경로가 하나뿐이어야 한다.

요코하마로 가는 접근성이 특히 중요하다. 고속도로망에는 중복이 없으므로, 자연재해로 구간 하나를 쓸 수 없게 되면 일부 도시는 요코하마에서 갈 수 없게 된다.

도시마다 인구와 경제 규모에 따라 중요도 값이 주어진다. 고속도로망이 주어졌을 때 한 구간에서 자연재해가 나면, 그 구간 때문에 요코하마에서 접근할 수 없게 되는 도시들의 중요도 합이 피해가 된다. 후보 구간마다 취약도도 평가된다. 구간의 위험도는 그 구간의 피해와 취약도를 곱한 값이고, 고속도로망의 총 위험도는 망에 속한 모든 구간 위험도의 합이다. 총 위험도의 최솟값을 구한다.

첫 줄에 정수 $n$과 $m$이 주어진다 ($2 \le n \le 10^5$, $1 \le m \le 3 \times 10^5$). 각각 도시의 수와 후보 구간의 수이다. 도시는 1번부터 $n$번까지 번호가 붙어 있으며, 1번이 요코하마이다.

둘째 줄에는 정수 $p_1, \dots, p_n$이 주어진다. 각 $p_i$ ($1 \le p_i \le 1000$)는 $i$번 도시의 중요도 값이다.

이어서 $m$개의 줄에 후보 구간이 주어진다. $j$번째 줄에는 정수 $u_j$, $v_j$, $q_j$가 주어지며, 이는 $u_j$번 도시와 $v_j$번 도시를 잇는 후보 구간의 취약도가 $q_j$라는 뜻이다 ($1 \le u_j < v_j \le n$, $1 \le q_j \le 10^6$). 같은 쌍 $(u_j, v_j)$는 한 번만 주어진다.

이 구간들 중 일부로 모든 도시를 연결하는 고속도로망을 만들 수 있음이 보장된다.

총 위험도의 최솟값을 한 줄에 출력한다.