요새화

허리케인이 다가오고 있다. 중요한 건물과 기반 시설은 여분의 물자를 비축하고, 발전기를 설치하고, 모래주머니나 다른 침수 방지 장치를 설치해 보강해야 한다. 각 보강 작업에는 시간이 걸리고 도로는 빠르게 침수되므로, 모든 계획을 제때 끝내지 못할 수도 있다. 도로 침수 제약 아래에서 완료할 수 있는 계획의 최대 개수를 구하라.

보강해야 할 위치 $i$의 목록과, 각 위치를 보강하는 데 걸리는 시간 $t_i$가 주어진다. 위치들은 도로망으로 연결되어 있다. 각 도로에는 침수되는 시각이 주어진다. 도로는 그 시각까지(그 시각 포함) 사용할 수 있고, 그 이후에는 사용할 수 없다. 이동은 보강 작업에 비해 매우 빠르므로 즉시 끝난다고 본다. 경로는 정비 차량의 안전한 기지인 위치 1에서 출발해 위치 1에서 끝나야 한다.

첫 줄에 데이터 세트의 수 $K$ ($1 \le K \le 100$)가 주어진다. 각 데이터 세트의 첫 줄에는 보강할 위치의 수 $n$과 도로의 수 $r$이 주어진다 ($1 \le n \le 1000$, $0 \le r \le 100000$).

다음 줄에는 위치 $i$를 보강하는 데 걸리는 시간 $t_i$가 $n$개의 정수로 주어진다 ($0 \le t_i \le 1000000$).

이어지는 $r$개의 줄에는 각각 정수 $a_j$, $b_j$, $f_j$가 주어진다 ($1 \le a_j, b_j \le n$, $0 \le f_j \le 1000000$). 도로 $j$는 위치 $a_j$와 $b_j$를 잇고, 양방향으로 사용할 수 있으며, 시각 $f_j$에 침수된다. 같은 두 끝점을 잇는 도로가 여러 번 나올 수 있다.

각 데이터 세트마다 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 세트 번호이다. 이어서 침수 제약 아래에서 보강할 수 있는 위치의 최대 개수를 출력한다. 각 데이터 세트 뒤에는 빈 줄을 출력한다.