최대 이익

새로운 기술이 이동 통신 시장을 뒤흔들고 있다. 대형 이동통신 사업자에게 이는 기회이자 도전이다. THU Group의 CS&T 통신 회사는 차세대 통신 기술에서 피할 수 없는 치열한 경쟁을 앞두고 있다. 준비해야 할 일이 매우 많다. 부지 선정만 해도 사전 시장 조사, 현장 답사, 최적화 등의 작업을 마쳐야 한다.

시장 조사와 현장 답사를 거쳐 회사는 이동 통신 신호 중계소를 세울 부지 N곳을 확정했다. 부지의 지리적 조건 때문에 중계소를 세우는 위치마다 초기 비용이 다르다. 다행히 이 비용 데이터는 사전 시장 조사에서 이미 파악했다. i번째 중계소를 세우는 데 드는 초기 비용은 Pi이다(1 ≤ i ≤ N).

회사는 예상 사용자층도 조사했으며, 이는 M개의 고객 그룹으로 이루어진다. i번째 그룹의 정보는 Ai, Bi, Ci 세 값으로 정리할 수 있다. 이 그룹의 사용자는 중계소 Ai와 Bi를 이용해 통신하며, 회사는 Ci의 수익을 얻는다(1 ≤ i ≤ M, 1 ≤ Ai, Bi ≤ N).

THU Group의 CS&T 회사는 세울 중계소를 선택해 그에 필요한 초기 비용을 지불하고, 특정 고객 그룹에 서비스를 제공해 수익을 얻을 수 있다. 회사가 가능한 한 많은 이익을 얻으려면 어떤 중계소를 세워야 하는가? (이익 = 총수익 − 총초기 비용)

입력의 첫째 줄에는 두 정수 N과 M이 주어진다.

둘째 줄에는 각 중계소를 세우는 데 드는 초기 비용 P1, P2, …, PN을 나타내는 N개의 정수가 주어진다.

이어서 M개의 줄이 주어진다. 입력의 (i + 2)번째 줄에는 i번째 고객 그룹의 정보를 나타내는 3개의 정수 Ai, Bi, Ci가 주어진다.

프로그램은 회사가 얻을 수 있는 최대 이익을 나타내는 정수 하나를 출력해야 한다.

N ≤ 5000, M ≤ 50000, 0 ≤ Ci ≤ 100, 0 ≤ Pi ≤ 100.