12936번 - 영웅은 죽지 않아요

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

각 영웅들에게는 메르시가 그들을 부활시키는 데에 필요한 에너지 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 이하의 정수입니다.

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