Problem
鉴于最近的窃听消息，两家强硬的互联网巨头 Uragania Laim.UR和“Xenda”决定签署协议，在彼此的数据中心之间建立安全的通信通道。乌拉干尼亚有n座城市，但遗憾的是，任何一座城市都没有两家巨头的数据中心。因此，要形成安全通道，就必须铺设远距离的通讯线路。
这些公司的专家已经确定了 m 对城市，这些城市可以通过铺设通信通道段来连接，并估算了为这些对中的每对创建这样一个段的成本。
生成的通道可能由多个段组成。起点必须是第一公司数据中心所在城市，可以经过中间城市，终点必须是第二公司数据中心所在城市。
现在有必要确定连接两家公司数据中心的安全通道的最低成本。
输入：
第一行包含整数 n 和 m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) —一条路段可以连接的城市数和城市对数。第二行包含 n 个整数 ai (0 ≤ a
i ≤ 2)。如果a
i = 0，那么第i个城市没有任何巨头的数据中心。如果ai = 1，那么“Laim.UR”数据中心位于第i个城市，如果a
i = 2，那么“Xenda”数据中心位于第i-第城市；.保证这些数字中至少有一个一和一个二。接下来的 m 行中的每一行都包含三个整数—— s
i , t
i 和 c
i ，表示城市 s
i 和 t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) 可以通过成本为 ci (1 ≤ ci ≤ 105 ) 的链接段连接。每对城市最多只能由一个通道段连接。
输出：
如果可以通过安全通信通道连接不同互联网巨头的两个数据中心，则在输出文件中打印三个数字：x、y 和 d，这意味着可以在城市 x 和 y 之间建立通信通道总成本 d．在 x 城市应该有一个数据中心“Laim.UR”，在城市 y ——数据中心“Xenda”。如果有多个最佳答案，请打印其中一个。如果无法绘制所需的通道，则打印−1。
例子
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
6 7
1 0 1 2 2 0
1 3 3
1 2 4
2 3 3
2 4 2
1 6 5
3 5 6
5 6 1
| 3 4 5 |
| 2 |
4 2
1 0 0 2
1 3 3
2 4 2
| -1 |
说明
在第一个例子中，最好从两个部分建立一个沟通渠道：3 − 2 和 2 减去； 4.