缺席使心变得更亲近。罗宾在大橡树完成训练的同时,玛丽安在市场上卖掉了她的最后一件商品。他们迫不及待地想见面,于是两人都毫不拖延地出发了。
出行网络表示为从 $$$1$$$ 到 $$$n$$$ 编号的 $$$n$$$ 顶点和 $$$m$$$ 边。第 $$$i$$$ 条边连接顶点 $$$u_i$$$ 和 $$$v_i$$$,并需要 $$$w_i$$$ 秒来运行(所有 $$$w_i$$$ 都是偶数)。 Marian 从顶点 $$$1$$$(市场)开始,Robin 从顶点 $$$n$$$(Major Oak)开始。
此外,$$$n$$$ 个顶点中的 $$$h$$$ 每个都有一匹可用的马。玛丽安和罗宾都是熟练的骑手,可以立即上马(即 $$$0$$$ 秒内)。骑行时旅行时间减半。一旦上马,马就可以完成剩下的旅程。会议必须发生在顶点上(即不是在边上)。两者都可以选择在任何顶点等待。
输出Robin和Marian最早见面的时间。如果顶点 $$$1$$$ 和 $$$n$$$ 断开连接,则输出 $$$-1$$$,因为会议被取消。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行由三个整数组成 $$$n$$$, $$$m$$$, $$$h$$$ ($$$2 \le n \le 2 \cdot 10^5, \;1 \le m \le 2 \cdot 10^5, \; 1 \le h \le n$$$) — 顶点数、边数和数量具有一匹马的顶点。
每个测试用例的第二行包含 $$$h$$$ 不同的整数 $$$a_1, a_2, \ldots, a_h$$$ ($$$1 \le a_i \le n$$$) - 拥有一匹可用马的顶点。
然后跟随每个测试用例的 $$$m$$$ 行,每行包含三个整数 $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1\le u_i,v_i \le n, \; 2\le w_i \le 10^6$$$) - 意味着顶点之间有一条边$$$u_i$$$ 和 $$$v_i$$$ 加上没有马的旅行成本 $$$w_i$$$ 秒。
没有自环或多重边。幸运的是,所有 $$$w_i$$$ 都是偶数。
保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,罗宾和玛丽安最早见面的时间。如果他们不可能相遇,则输出$$$-1$$$。
示例
输入 #1
6 2 1 1 1 1 2 10 3 1 2 2 3 1 2 10 3 3 1 2 1 2 4 1 3 10 2 3 6 4 3 2 2 3 1 2 10 2 3 18 3 4 16 3 2 1 2 1 2 4 1 3 16 7 7 1 3 1 5 2 2 6 12 1 2 12 6 4 8 7 3 4 6 3 4 7 6 4
输出 #1
5 -1 6 19 14 12
注意
在第一个测试用例中,Marian 从顶点 $$$1$$$ 骑行到顶点 $$$2$$$,Robin 等待。
在第二个测试用例中,顶点 $$$1$$$ 和 $$$3$$$ 未连接。
在第三个测试用例中,Marian 和 Robin 都前往顶点 $$$2$$$ 见面。
在第四个测试用例中,Marian 在没有马的情况下前往顶点 $$$2$$$,在顶点 $$$2$$$ 上马,然后骑到顶点 $$$3$$$ 去见 Robin。
在第五个测试用例中,Marian 在没有马的情况下前往顶点 $$$2$$$,在顶点 $$$2$$$ 上马,骑回顶点 $$$1$$$,然后到达顶点 $$$3$$$。罗宾等待着。