该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在由 N 个城市（编号 1~N）构成的新世界中，“星轨联邦”与“地核同盟”因能源技术路线分歧形成对峙。1 号城市为“星轨联邦”的核心城市，2 号城市是“地核同盟”的核心城市。

现在，在 1 号城市卧底的“地核同盟”科学家截获了重要情报——“星轨联邦”的能源武器即将研究完成。为了尽快将情报传递给同盟头脑，科学家需将加密数据从 1 号城市紧急传输至 2 号城市。

由于两大阵营进入了“轨道-地核双重封锁”状态，传输路径仅允许存在 一次阵营跃迁（即在传输过程中，跨越联邦和同盟管辖区的通道只能有一条，否则数据就会被拦截），请帮助卧底科学家选择总耗时最短的传输路线。

输入格式

输入文件：confront.in

第一行包含两个整数 N 和 M，分别表示城市的数量和城市间道路的数量，路线都是双向的，且两个城市之间只有一条路线。

接下来 M 行，每行包含三个整数 A, B, S，表示城市 A 和城市 B 之间存在一条路线，数据在这条路线上传输时间为 S。

最后一行包含 N 个整数 1 或 2，其中的第 i 个整数表示城市 i 所属的阵营，为 1 则表示隶属于“星轨联邦”，为 2 则表示隶属于“地核同盟”。

输出格式

输出文件：confront.out

输出一行，表示最短的传输时间。如果无法完成数据传输，则输出 -1。

输入样例 1

3 2
1 2 80
3 2 40
1 2 1

输出样例 1

80

输入样例 2

4 3
1 4 50
4 3 100
2 3 80
1 2 1 2

输出样例 2

-1

输入样例 3

6 7
6 1 100
4 3 10
2 5 30
4 6 30
1 3 120
6 5 20
2 4 40
1 2 1 2 2 1

输出样例 3

150

数据范围

• 对于 20% 的数据，2 ≤ N ≤ 30，M = 1。
• 对于 100% 的数据，2 ≤ N ≤ 600，0 ≤ M ≤ 10000，1 ≤ X, Y ≤ N，1 ≤ T ≤ 500。