시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 16 6 6 50.000%

문제

모든 영웅이 죽었을 때에 메르시가 말합니다. ‘영웅은 죽지 않아요.’

각 영웅들에게는 메르시가 그들을 부활시키는 데에 필요한 에너지 P(i)가 부여되어 있습니다. 그리고 영웅과 영웅 사이에는 어떤 관계가 있을 수 있는데, 함께 부활한다면 C(i)의 에너지를 되돌려줍니다.

즉, 메르시가 K(0≤K≤N)명의 영웅들을 부활시킨다면, 회복되는 관계들에서 얻어지는 에너지의 합에서 영웅들을 부활시키는 데에 필요한 에너지의 합을 뺀 만큼의 에너지를 얻을 수 있습니다. 이때, 메르시가 영웅 몇 명을 부활시켜 최대량의 에너지를 얻고자 합니다. 메르시가 얻을 수 있는 최대 에너지량을 구하는 프로그램을 작성하세요.

입력

첫째 줄에 영웅의 수와 영웅 사이의 관계의 수를 나타내는 두 정수 N (1≤N≤5,000)과 M(0≤M≤50,000)이 주어집니다.

둘째 줄에 각 영웅을 부활시키는 데에 필요한 에너지를 나타내는 N개의 정수 P(i)가 주어집니다.

셋째 줄부터 M개의 줄에 걸쳐 3개의 정수 A(i) B(i) C(i)가 주어집니다.

A(i)와 B(i)는 영웅의 번호이며 1부터 N 사이의 값을 가집니다. C(i)와 P(i)는 모두 0 이상 100 이하의 값을 가집니다.

출력

메르시가 얻을 수 있는 최대 에너지를 출력하세요.

예제 입력 1

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

예제 출력 1

4