착륙 수수료

시간 제한5초메모리 제한1024 MB

요약

행성마다 착륙 요금이 있고 한 행성을 특정 구간의 행성들과 연결할 수 있습니다. 모든 행성을 잇는 최소 노선 비용을 구합니다.

난이도: 보통10점 중 6점
유형: 최소 신장 트리, 유니온 파인드, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

먼 은하계에서 저예산 신생 우주 항공사가 행성 간 비행을 시작하려 합니다. 은하계에는 1부터 $n$ 까지 번호가 붙은 행성 $n$ 개가 있습니다. 행성 $a$ 와 행성 $b$ 사이에 매일 양방향 항공편을 개설하는 비용은 두 행성의 착륙 및 이륙 수수료에만 따라 정해집니다. 행성 $k$ 의 수수료는 $p_k$ 이므로, $a$ 와 $b$ 를 잇는 노선의 비용은 $p_a + p_b$ 입니다.

그림 1: 두 번째 테스트 데이터의 그림입니다. 행성 노드 안에 각 행성의 수수료가 적혀 있습니다. 최적 선택에 포함된 노선은 굵게 표시되어 있습니다.

항공사는 어느 행성에서든 직접 또는 다른 행성을 거쳐 나머지 모든 행성에 갈 수 있도록 모든 행성을 연결하려 합니다. 아무 두 행성 사이에나 노선을 열 수 있는 것은 아닙니다. 허용된 쌍에만 노선을 열 수 있으며, 허용 조건은 $x_k$ $a_k$ $b_k$ 형태의 허가증 $m$ 개로 주어집니다. 허가증 하나는 행성 $x_k$ 와 $a_k \le c \le b_k$ 를 만족하는 모든 행성 $c$ 사이에 노선을 열 수 있다는 뜻입니다.

모든 행성이 연결되도록 노선을 열 때 필요한 최소 총 비용을 구하십시오.

입력

첫 줄에는 행성의 수 $n$ 과 허가증의 수 $m$ 이 자연수로 주어집니다. 둘째 줄에는 각 행성의 수수료 $p_1, p_2, \ldots, p_n$ 이 공백으로 구분되어 주어집니다. 이어지는 $m$ 개의 줄 가운데 $k$ 번째 줄에는 $k$ 번째 허가증을 나타내는 자연수 $x_k$ , $a_k$ , $b_k$ 가 있습니다.

제약은 $0 \le p_k \le 10^6$ , $1 \le x_k \le n$ , $1 \le a_k \le b_k \le n$ 입니다. 또한 $x_k$ 는 $a_k$ 와 $b_k$ 사이에 있지 않으며, $x_k < a_k$ 또는 $b_k < x_k$ 입니다. 같은 값의 허가증이 여러 개 있을 수 있고, 같은 노선이 여러 허가증에 나타날 수도 있습니다. 입력은 항상 모든 행성을 연결할 수 있도록 주어집니다.

출력

모든 행성을 연결하는 데 필요한 최소 총 비용을 출력하십시오.

예제3

예제 1
입력
```
4 4
2 4 1 0
1 2 3
1 3 4
3 1 1
4 1 2
```
예상 출력
```
9
```

예제 2

입력

6 8
3 5 8 2 9 4
3 1 2
6 3 3
3 1 1
6 2 2
2 3 6
3 1 2
3 2 2
4 1 1

예상 출력

예제 3

입력

12 10
9 2 7 5 5 9 3 6 5 7 8 8
6 3 3
9 1 1
6 10 11
1 3 11
5 6 12
3 5 5
12 3 7
6 1 4
4 6 6
10 4 6

예상 출력