Problem
오늘, Aisne Castle에서는 n개의 베이커리가 참여하는 파이 축제를 개최합니다. 각 베이커리는 1부터 n까지의 고유 번호를 가지고 있습니다.
일부 빵집은 양방향 도로로 연결되어 있지만 빵집 i에서 빵집 j까지 도보로 이동할 수 있는 경우 그 사이에는 정확히 하나의 경로가 있습니다.
En은 i번째 빵집에서 파이를 먹으면 A
i 기쁨을 얻습니다. 그리고 숫자 v와 u가 있는 빵집 사이의 길을 따라 지나가면 맛있는 파이 향이 C
v,u 기쁨을 가져다줍니다.
En은 모든 빵집에 한 번 이상 가고 싶지 않지만(일부는 전혀 가지 않을 수도 있음) 축제를 최대한 활용하고 싶어합니다.
그는 빵집 중 한 곳에서 시작하여 기존 도로를 이용해서만 빵집 사이를 건널 것입니다.
En이 얻을 수 있는 최대의 즐거움을 결정하도록 도와주세요.
입력:
첫 번째 줄에는 숫자 n(1 <= n <= 50000) - 빵집의 수와 숫자 k - 빵집 사이에 존재하는 도로의 수가 포함됩니다.
두 번째 줄에는 n개의 숫자 A
i(0 <= A
i <= 10000)가 포함되어 있습니다 - i번째 빵집에서 파이의 즐거움.
그런 다음 각각 3개의 숫자 v, u, C(1 <= v, u <= n; v ≠ u; 0 <= C <= 10000)를 포함하는 k개의 라인이 이어지며, 이는 그 사이에 도로가 있음을 의미합니다. v와 u로 번호가 매겨진 빵집과 이 길의 향기는 C 기쁨을 가져다줍니다.
출력:
하나의 숫자를 인쇄하십시오 - 가능한 최대 만족.
예:
<몸>
| 입력 |
출력 |
2 1
1 1
1 2 1
| 3 |
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
| 37 |
설명:
첫 번째 예에서는 첫 번째 빵집(1단)에서 시작하여 첫 번째와 두 번째 빵집 사이의 길을 따라 걷고(1단) 두 번째 빵집(1단)을 방문해야 합니다. 완전한 즐거움 - 1+1+1 = 3.
두 번째 예에서는 5번째 빵집(10가지 즐거움)에서 시작하여 5번째와 4번째 빵집(1가지 즐거움) 사이의 길을 따라 걷고 4번째 빵집(6가지 즐거움)을 방문하고 4번째와 2번째 사이의 길을 따라야 합니다. 베이커리(1개), 2번째 베이커리 방문(5개), 2번째와 3번째 베이커리 사이의 길을 따라 걷기(10개), 3번째 베이커리 방문(4개) 완전한 즐거움 - 10+1+6+1+5+10+4 = 37.