보안 연결

최근 통신 회선 도청 사건이 알려지면서, 우라가니아의 두 인터넷 대기업 Laim.UR과 Xenda가 서로의 데이터 센터를 연결하는 보안 통신 회선을 설치하기로 합의했다. 우라가니아에는 $n$개의 도시가 있지만, 안타깝게도 두 대기업의 데이터 센터가 함께 있는 도시는 하나도 없다. 따라서 보안 회선을 구성하려면 도시 사이에 통신 선로를 새로 깔아야 한다.

각 회사의 전문가들은 통신 회선 구간을 깔아 연결할 수 있는 도시 쌍 $m$개를 정하고, 각 쌍마다 그러한 구간을 만드는 비용을 산정했다.

완성된 회선은 여러 구간으로 이루어질 수 있다. 회선은 첫 번째 회사의 데이터 센터가 있는 도시 중 하나에서 시작하고, 중간 도시를 지날 수 있으며, 두 번째 회사의 데이터 센터가 있는 도시에서 끝나야 한다.

이제 두 회사의 데이터 센터를 연결하는 보안 회선의 최소 비용을 구해야 한다.

첫째 줄에 정수 $n$과 $m$이 주어진다 ($2 \le n \le 5\,000$, $1 \le m \le 10^5$). 각각 도시의 수와 통신 회선 구간으로 연결할 수 있는 도시 쌍의 수다.

둘째 줄에 $n$개의 정수 $a\_i$가 주어진다 ($0 \le a\_i \le 2$). $a\_i = 0$이면 $i$번째 도시에 두 대기업 중 어느 쪽의 데이터 센터도 없다. $a\_i = 1$이면 $i$번째 도시에 Laim.UR의 데이터 센터가 있고, $a\_i = 2$이면 $i$번째 도시에 Xenda의 데이터 센터가 있다. 이 수들 가운데 1과 2가 각각 적어도 하나씩 있음이 보장된다.

다음 $m$개 줄에는 각각 세 개의 정수 $s\_i$, $t\_i$, $c\_i$가 주어진다. 이는 도시 $s\_i$와 $t\_i$ ($1 \le s\_i, t\_i \le n$, $s\_i \ne t\_i$)를 비용 $c\_i$ ($1 \le c\_i \le 10^5$)인 통신 회선 구간으로 연결할 수 있음을 뜻한다. 각 도시 쌍은 통신 회선 구간 하나로만 연결할 수 있다.

서로 다른 인터넷 대기업의 데이터 센터 두 곳을 보안 통신 회선으로 연결할 수 있다면, 세 수 $x$, $y$, $d$를 출력한다. 이는 도시 $x$와 $y$ 사이에 총비용 $d$인 통신 회선을 놓을 수 있음을 뜻한다. 도시 $x$에는 Laim.UR의 데이터 센터가, 도시 $y$에는 Xenda의 데이터 센터가 있어야 한다. 최적해가 여러 개라면 그중 아무거나 출력한다. 해당 회선을 놓을 수 없다면 $-1$을 출력한다.

첫 번째 예제에서는 두 구간 $3-2$와 $2-4$로 통신 회선을 구성하는 것이 최적이다.