영웅은 죽지 않아요

시간 제한2초메모리 제한512 MB

요약

되살릴 영웅의 부분집합을 골라 양 끝이 모두 선택된 결속의 보상을 얻고, 보상 합에서 부활 비용을 뺀 값이 최대가 되게 한다.

난이도: 어려움10점 중 8점
유형: 그래프, 최소 신장 트리, 그리디, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

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

영웅 $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 이하의 정수이다.

출력

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

예제9

예제 1

입력

예상 출력

예제 2
입력
```
1 0
0
```
예상 출력
```
0
```
예제 3
입력
```
1 0
100
```
예상 출력
```
0
```
예제 4
입력
```
2 1
100 100
1 2 100
```
예상 출력
```
0
```
예제 5
입력
```
2 1
10 20
1 2 100
```
예상 출력
```
70
```
예제 6
입력
```
3 3
0 0 0
1 2 0
2 3 0
1 3 0
```
예상 출력
```
0
```

예제 7

입력

4 3
100 100 1 1
1 2 100
1 2 100
3 4 5

예상 출력

예제 8

입력

6 6
5 5 5 100 100 100
1 2 6
2 3 6
1 3 6
4 5 100
5 6 100
4 6 100

예상 출력

예제 9

입력

예상 출력