Escape Room Key Adventure

Architect Timothy has designed a new escape room game. The game consists of n rooms labeled from \(0\) to \(n-1\). Initially, each room \(i\) contains exactly one key of type \(r[i]\) (an integer in the range \(0\) to \(n-1\)). Note that the keys’ types are not necessarily distinct.

There are also m bidirectional corridors labeled from \(0\) to \(m-1\). The \(j\)th corridor connects two different rooms \(u[j]\) and \(v[j]\). (There may be multiple corridors connecting the same pair of rooms.)

When playing the game, a player may perform the following operations while in a room \(x\):

• Collect the key in room \(x\) (of type \(r[x]\)) if it has not been collected before.
• Pass through a corridor \(j\) if room \(x\) is one of its endpoints (i.e. \(u[j] = x\) or \(v[j] = x\)) and the player has already collected a key of type \(c[j]\). Passing through corridor \(j\) moves the player from one endpoint to the other.

Note that any key collected by the player is kept forever and may be used any number of times.

The game starts in a room \(s\) with no keys. A room \(t\) is considered reachable from \(s\) if the player can reach \(t\) from \(s\) by a sequence of the above operations. Define \(p[i]\) as the number of rooms reachable when starting from room \(i\) (including the starting room itself).

Your task is to find the set of room indices \(i\) for which \(p[i]\) is minimized. Print these indices in increasing order, separated by a space.

Note on the game mechanism: When starting from room \(s\), the player should first collect the key in that room. Then, if a corridor \(j\) connects a room that has been reached with a room not reached yet, and if the required key type \(c[j]\) is present among the keys collected from reached rooms, the player can pass through to the other room, collect its key, and so on. The process repeats until no more rooms can be reached.

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the number of rooms and corridors, respectively.

The second line contains \(n\) integers \(r[0], r[1], ..., r[n-1]\) where \(r[i]\) is the type of the key in room \(i\).

Each of the next \(m\) lines contains three integers \(u, v, c\) describing a corridor connecting rooms \(u\) and \(v\) which can be passed only if the player has a key of type \(c\).

outputFormat

Output the indices of the rooms (in increasing order separated by a single space) for which \(p[i]\) (the number of rooms reachable starting from room \(i\)) is minimized.

sample

3 3
0 1 2
0 1 0
1 2 1
0 2 2

0 1 2