题目描述

紫堂幻为了提高他三只小斯巴达的智商和能力,把他们丢到了试炼幻境中历练。
Deeq9f.jpg
这个幻境中有$n$个城镇,城镇之间由$m$条双向道路相连。每个城镇都由一个怪物镇守,当且仅当一个城镇的怪物被打败后,才能通过该城镇。否则只能待在此城镇中,无法离开。幻境中的怪物分为了三个级别$1,2,3$,其中$1$级怪物只有一只,为幻境之主。而以小斯巴达的能力只能打败$3$级怪物,大斯巴达则可以打败幻境中任意级别的怪物。只有三只小斯巴达在同一城镇相遇后,才能合体为大斯巴达。
三只小斯巴达进入幻境后被分开到了三个互不相同的初始城镇,当且仅当他们打败幻境之主后才能离开幻境。弱小可怜又无助的小斯巴达们找到了你,因为体力有限,它们希望走的路越短越好。希望你可以告诉它们能离开幻境的最短路长度(最短路长度=小斯巴达合体前分别走过的距离之和+合体后大斯巴达走过的距离)。
如果它们无法逃离幻境,则输出$-1$。
幻境保证起始点与幻境之主所在城镇连通,可能有重边和自环。


输入格式

第一行两个整数$n,m$。$1\leq{n,m}\leq200000$
第二行$n$个整数$a_i$,表示第$i$个城镇中的怪物级别,$a_i∈\lbrace1,2,3\rbrace$。
接下来$m$行,每行包含三个整数$u,v,w$,表示城镇$u$和$v$之间有一条长度为$w$的路径($1\leq{u,v}\leq{n},1\leq{w}\leq10^7$)。
最后三个互不相同的整数$A,B,C$,表示三只小斯巴达刚进入幻境的初始城镇。保证小斯巴达能够打败初始城镇的怪物。


输出格式

输出一个整数,表示小斯巴达们可以离开幻境的最短路长度。


样例数据

输入

5 6
3 3 3 3 1
1 4 2
1 5 1
2 4 4
2 5 3
3 4 1
4 5 2
1 2 3

输出

7

备注

  • 可以先合体,再打怪。
  • 合体为大斯巴达后所走过的道路长度只需被计算一次。
  • 打败怪物的时间忽略不计,即可以理解为只要实力大于怪物就能秒杀。

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务