Fortification

A hurricane is approaching. Critical buildings and infrastructure must be fortified by adding extra supplies, installing power generators, or placing sandbags and other flood barriers. Each fortification takes time, and roads flood quickly, so not every plan may be finished in time. Find the maximum number of plans that can be finished under the road flooding constraints.

You are given a list of locations $i$ that need fortification, and for each location the time $t_i$ it takes to fortify. A road network connects the locations. For each road, you are given the time it floods. A road can be used up to and including that time, but not later. Driving is instantaneous, since it is fast compared to fortification. Your route must start and end at location 1, the safe depot for the maintenance vehicle.

The first line contains $K$ ($1 \le K \le 100$), the number of data sets. Each data set begins with two integers $n$ and $r$ ($1 \le n \le 1000$, $0 \le r \le 100000$), the number of locations to fortify and the number of roads.

The next line contains $n$ integers $t_i$ ($0 \le t_i \le 1000000$), the time to fortify location $i$.

Each of the next $r$ lines contains three integers $a_j$, $b_j$, $f_j$ ($1 \le a_j, b_j \le n$, $0 \le f_j \le 1000000$). Road $j$ connects $a_j$ and $b_j$, can be used in both directions, and floods at time $f_j$. The same pair of endpoints may appear more than once.

For each data set, print Data Set x: on its own line, where $x$ is the data set number. Then print the maximum number of locations that can be fortified under the flooding constraints. Print a blank line after each data set.