Farmer John은 게을러져 모든 목장 $N$개 ($5\le N\le10{,}000$), 번호 $1\ldots N$에 가는 길을 관리하고 싶지 않다. 각 목장에 소 하나가 산다. 연결을 유지하며 길 $P$개 ($N-1\le P\le100{,}000$)를 최대한 없앤다. 남길 $N-1$개를 정해야 한다.

양방향 길 $j$는 $S_j,E_j$ ($1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$)를 잇고 시간 $L_j$ ($0\le L_j\le1{,}000$)가 든다. 각 목장 쌍 직접 길은 최대 하나다.

교통 감소로 소가 슬퍼한다. 위로하려 매일 각 소를 최소 한 번 방문한다. 목장 $i$를 방문할 때마다 그냥 지나가도 $C_i$ ($1\le C_i\le1{,}000$) 시간 대화한다.

소가 회복할 때까지 선택한 같은 목장에서 매일 잔다. 그 소와는 최소 아침에 깨어날 때와 저녁에 자러 돌아온 때 대화한다.

FJ가 제안한 길을 남기고 최적 잠자리 목장을 고르면 매일 각 소를 최소 한 번 방문할 최소 총 시간을 구하자.

처음 $10$번 제출은 실제 테스트 일부의 실행 결과를 받는다.

입력

• 줄 $1$: 공백 구분 정수 $N,P$.

• 줄 $2\ldots N+1$: 줄 $i+1$에 정수 $C_i$.

• 줄 $N+2\ldots N+P+1$: 줄 $N+j+1$에 공백 구분 정수 $S_j,E_j,L_j$.

출력

• 줄 $1$: 잠자리 목장 소의 두 방문을 포함한 전체 방문 시간 정수.

예제

입력 1

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

출력 1

176

참고

              +-(15)-+
             /        \
            /          \
     1-(5)-2-(5)-3-(6)--5
            \   /(17)  /
         (12)\ /      /(12)
              4------+

이 길들을 남긴다:

     1-(5)-2-(5)-3      5
            \          /
         (12)\        /(12)
             *4------+

$4$에서 깨어나 $4,5,4,2,3,2,1,2,4$ 순으로 방문하여 자기 전 시간 $176$이 든다.

서브태스크

점수: $300$

문제 출제: David Benjamin, Jacob Steinhardt, 2008