Vacation Plans

A group of $p$ people plans a winter vacation on a remote island near the equator. Every member lives in a different country, and the island is reachable only by airplane. Each country has exactly one airport, so every member has to reach the airport city of their own country. The group agreed that everyone is at their airport on the same day, and that day does not have to be the first day of the trip.

Each country has $n$ cities and $m$ one way roads. City 1 is the home city, and city $a$ holds the airport. On day 0 every member is in city 1 of their own country. On each day after that, a member either travels along one road out of the current city, or stays in the current city. Travelling from city $u$ to city $v$ along a road costs $g$, and staying in city $v$ costs the cheapest hotel price $h_v$ of that city. Every member picks exactly one of the two options every day.

The members pool their money, so they plan as a group. After the same number of days $D$, every member has to be in the airport city of their own country. $D$ can be 0. Find the smallest possible total cost.

Roads are directed, and the cost from $u$ to $v$ does not have to equal the cost from $v$ to $u$. No road connects a city to itself. In every country at least one route runs from city 1 to the airport city.

Figure L.1. The city layouts of two members. The airports are in city 4 and city 3, and the home city is 1 for both. $g$ is the cost of travelling along a road, and $h$ is the cheapest hotel price.

In Figure L.1 the cheapest plan works like this. On day 1 the first member moves to city 3 and the second member moves to city 2. On day 2 the first member moves to city 4 and the second member moves back to city 1. On day 3 the first member stays in city 4 and the second member moves to city 3. The cost is $(1 + 5 + 1) + (3 + 2 + 4) = 16$.

The first line contains the integer $p$, the number of members in the group and therefore also the number of countries ($1 \le p \le 3$).

The descriptions of the $p$ countries follow. The first line of a country description contains two integers $n$ and $m$, the number of cities and the number of roads ($1 \le n \le 50$, $n - 1 \le m \le 4n$). The next $n$ lines contain one integer each, the cheapest hotel price of city 1 through city $n$ in that order ($0 \le h \le 1{,}000{,}000$). The next $m$ lines each contain three integers $u$, $v$ and $g$, meaning that a one way road runs from city $u$ to city $v$ at cost $g$ ($1 \le u, v \le n$, $u \ne v$, $0 \le g \le 1{,}000{,}000$). The last line of a country description contains the integer $a$, the city that holds the airport ($1 \le a \le n$). City 1 is the home city in every country.

Print one line with a single integer, the smallest total cost that puts every member in the airport city of their own country after the same number of days.