Secure Connection

After recent news about wiretapping of communication channels, two rival internet giants of Uragania, Laim.UR and Xenda, agreed to establish a secure communication channel between each other's data centers. Uragania has $n$ cities, but unfortunately no city hosts data centers of both giants. So building the secure channel requires laying intercity communication lines.

Specialists of the companies identified $m$ pairs of cities that can be joined by laying a segment of the communication channel, and estimated the cost of building such a segment for each pair.

The resulting channel may consist of several segments. It must start in one of the cities hosting a data center of the first company, may pass through intermediate cities, and must end in a city hosting a data center of the second company.

Now you need to determine the minimum cost of a secure channel connecting the two companies' data centers.

The first line contains integers $n$ and $m$ ($2 \le n \le 5\,000$, $1 \le m \le 10^5$): the number of cities and the number of pairs of cities that can be joined by a segment of the communication channel.

The second line contains $n$ integers $a\_i$ ($0 \le a\_i \le 2$). If $a\_i = 0$, city $i$ hosts no data center of either giant. If $a\_i = 1$, city $i$ hosts a Laim.UR data center, and if $a\_i = 2$, city $i$ hosts an Xenda data center. It is guaranteed that among these numbers there is at least one 1 and at least one 2.

Each of the following $m$ lines contains three integers $s\_i$, $t\_i$, and $c\_i$, meaning that cities $s\_i$ and $t\_i$ ($1 \le s\_i, t\_i \le n$, $s\_i \ne t\_i$) can be joined by a segment of the communication channel with cost $c\_i$ ($1 \le c\_i \le 10^5$). Each pair of cities can be joined by at most one segment of the channel.

If two data centers of different internet giants can be connected by a secure communication channel, output three numbers $x$, $y$, and $d$, meaning that a communication channel with total cost $d$ can be laid between cities $x$ and $y$. City $x$ must host a Laim.UR data center, and city $y$ must host an Xenda data center. If there are several optimal answers, output any of them. If the channel cannot be built, output $-1$.

In the first example, the optimal channel consists of two segments: $3-2$ and $2-4$.