영웅은 죽지 않아요

모든 영웅이 쓰러지자 메르시가 말한다. "영웅은 죽지 않아요."

영웅 $i$를 부활시키려면 에너지 $P(i)$가 든다. 영웅 사이에는 관계가 있을 수 있고, 관계로 이어진 두 영웅이 함께 부활하면 그 관계에서 에너지 $C(i)$를 돌려받는다.

메르시가 영웅 $K$명($0 \le K \le N$)을 부활시키면, 두 영웅이 모두 부활한 관계에서 돌려받는 에너지의 합에서 부활에 쓴 에너지의 합을 뺀 만큼 에너지를 얻는다. 메르시가 얻을 수 있는 에너지의 최댓값을 구하라.

$K = 0$도 고르는 방법이므로 답은 항상 0 이상이다.

첫째 줄에 영웅의 수 $N$($1 \le N \le 5000$)과 관계의 수 $M$($0 \le M \le 50000$)이 공백을 두고 주어진다.

둘째 줄에 각 영웅을 부활시키는 데 드는 에너지 $P(1), P(2), \dots, P(N)$이 주어진다.

셋째 줄부터 $M$개 줄에 관계가 한 줄에 하나씩 $A(i)\ B(i)\ C(i)$ 형식으로 주어진다. $A(i)$와 $B(i)$는 1 이상 $N$ 이하의 서로 다른 영웅 번호이고, 같은 쌍이 여러 관계로 주어질 수도 있다. $P(i)$와 $C(i)$는 모두 0 이상 100 이하의 정수이다.

메르시가 얻을 수 있는 에너지의 최댓값을 한 줄에 출력한다.