유럽 여행

한 여행자가 유럽의 여러 나라를 여행하려고 한다. 방문해야 할 나라는 N개이며, 1번부터 N번까지 번호가 붙어 있다. 나라 사이를 잇는 양방향 길은 P개이다.

여행을 시작하기 전에 모든 나라가 서로 연결되어 있기만 하다면 길을 일부 지워도 된다. 즉, 모든 나라를 연결하는 N-1개의 길만 남긴다고 생각할 수 있다.

길을 지날 때마다 그 길의 통행 비용을 내야 한다. 또한 어떤 나라에 도착할 때마다 그 나라의 방문 비용도 내야 한다. 처음 출발할 나라는 자유롭게 정할 수 있으며, 출발할 때도 그 나라에 도착한 것으로 보아 방문 비용을 낸다. 길과 나라는 여러 번 지나거나 방문할 수 있고, 여행은 출발한 나라에서 끝나야 한다.

모든 나라를 적어도 한 번 방문하고 출발한 나라로 돌아오기 위한 최소 총비용을 구하라.

첫 줄에 나라의 수 N과 길의 수 P가 주어진다. 제한은 5 <= N <= 10,000, N-1 <= P <= 100,000 이다.

다음 N개의 줄에는 방문 비용이 주어진다. 이 중 i번째 줄에는 i번 나라에 도착할 때마다 드는 비용 C_i가 주어진다. 각 비용은 1 <= C_i <= 1,000 을 만족한다.

다음 P개의 줄에는 길의 정보 S_j, E_j, L_j가 주어진다. 이는 S_j번 나라와 E_j번 나라를 잇는 길을 지날 때 비용 L_j가 든다는 뜻이다. 두 끝점은 서로 다르며, 0 <= L_j <= 1,000 이다.

여행을 마치기 위한 최소 총비용을 출력한다.

남긴 길들이 트리라면 모든 나라를 방문하고 돌아오는 닫힌 여행에서는 남긴 각 길을 두 번씩 지나게 된다. 시작 나라는 방문 비용이 한 번 더 더해지므로, 방문 비용이 가장 작은 나라에서 시작하는 것이 최적이다.