Angry Cows#10664

Angry Cows

6 seconds

256 megabytes

Medium

In recent years, there has been a rapid spread of Extremely Green Oxen Illness (EGOI) — a disease that makes cows dangerous for tourists. After several incidents, it was decided that we must separate the areas where cows graze from the areas visited by tourists.

You have a map of the Alps. The map consists of $n$ regions. Each region can be either inhabited by cows, a tourist region, or empty. Some pairs of these regions are connected by bidirectional roads. Each road has a non-negative length. (In terms of graph theory, the map is an undirected weighted graph.)

You can build walls in some regions. Once you build a wall in a region, that region becomes inaccessible to both cows and tourists — they can no longer pass through that region.

Your task is to choose a set of regions where walls will be built. This set of regions must satisfy the following conditions:

It consists only of empty regions.
It must separate the cow regions from the tourist regions. This means cows must not be able to reach any tourist regions via roads (without passing through a region with a wall).
It must not separate tourist regions from each other. That is, tourists must be able to travel between any two tourist regions via roads (without passing through any region with a wall).

If there are several ways to achieve the above, we are only concerned with the ease of wall maintenance. The walls are maintained by special teams. There is exactly one such team in each tourist region.

For any region $A$ , we define its remoteness as the minimal length of a path between $A$ and some tourist region. (Path length is the sum of road lengths. Note that the path may pass through walls and cow regions — the maintenance team servicing the wall can freely move anywhere using any means.)

The remoteness of a set of regions is the maximum remoteness of any region in this set.

Among all sets of wall regions that satisfy all the given conditions, find and return a set with the smallest possible remoteness. If there are several such sets, return any one of them.

Note that the number of selected regions does not matter. In other words, you are not required to use the minimum number of walls.

Input

The first line contains two integers $n$ and $m$ ( $2 \leq n \leq 3 \cdot 1 0^{5}$ 2 \leq n \leq 3 \cdot 10^5, $n - 1 \leq m \leq 3 \cdot 1 0^{5}$ n-1 \leq m \leq 3 \cdot 10^5) — the number of regions and roads, respectively. The regions are numbered from $1$ to $n$ .

The second line contains $n$ integers $t_{1}, \dots, t_{n}$ t_1, \ldots, t_n, where $t_{i}$ t_i is $- 1$ if the $i$ -th region is inhabited by cows, $0$ if it is empty, and $1$ if it is a tourist region.

The next $m$ lines describe the roads. The $j$ -th line contains three integers $a_{j}$ a_j, $b_{j}$ b_j, and $ℓ_{j}$ \ell_j ( $1 \leq a_{j} < b_{j} \leq n$ 1 \le a_j < b_j \le n, $0 \leq ℓ_{j} \leq 1 0^{9}$ 0 \le \ell_j \le 10^9), representing a road between regions $a_{j}$ a_j and $b_{j}$ b_j of length $ℓ_{j}$ \ell_j.

It is guaranteed that:

there is at most one road connecting any two regions,
currently it is possible to travel between any two regions, using zero or more roads,
there is at least one region inhabited by cows,
there is at least one tourist region.

Output

If it is impossible to build walls as stated in the problem, output -1.

Otherwise, the first line should contain the number $k$ — the number of regions where you want to build walls. The second line should contain $k$ integers — the numbers of the regions where you want to build walls. (These numbers must be distinct, between $1$ and $n$ , inclusive. They do not need to be in any particular order.)

Your output will be accepted if the set meets all requirements and its remoteness is minimal.

Examples

Example 1

Example 2

Example 3

Note

In all examples, blue denotes tourist regions, brown denotes regions inhabited by cows, and orange denotes walls.

In the first example, the minimal possible remoteness is $2$ , achieved by placing walls in regions $4$ , $5$ , and $6$ . Note that we cannot place walls in regions $4$ , $2$ , and $6$ , even though we get remoteness $1$ , because then it would be impossible to travel between tourist regions $1$ and $3$ without passing through walls.

In the second example, the remoteness of region $2$ is $1000$ , the remoteness of region $3$ is $30$ , since this can be achieved via the path $1$ – $5$ – $4$ – $3$ . (Reminder: teams can move through walls and cow regions.) Therefore, we should place walls in regions $5$ and $3$ (not $2$ ), which gives a remoteness of $30$ .

Scoring

Block $1$ ( $7$ points): $n \leq 10$ n \le 10.

Block $2$ ( $22$ points): all lengths $ℓ_{j} = 0$ \ell_j = 0.

Block $3$ ( $16$ points): there is exactly one tourist region.

Block $4$ ( $11$ points): there are exactly $n - 1$ n-1 roads (that is, the graph is a tree).

Block $5$ ( $8$ points): $n, m \leq 2000$ n, m \le 2000 and all lengths $ℓ_{j} = 1$ \ell_j = 1.

Block $6$ ( $36$ points): no additional constraints.