9590 - 翻修道路

通过次数

0

提交次数

0

时间限制 : 3 秒
内存限制 : 1024 MB

C 国中包含 n 座城市,这些城市通过 m 条双向道路连接。城市从 1n 编号,道路从 1m 编号,i 号道路两端连接着城市 u_i 与城市 v_i,它的长度为 w_i 米。经由这些道路,从 C 国中任意一个城市出发,均能到达其他所有城市。

C 国人民喜欢环路旅程,但又不喜欢经过太多条道路,为此 C 国的道路被建造得非常特殊。更具体地,对于一条经过 l 条道路的简单环路(即除起点城市外不经过重复城市的环路),它可以表示为 $c{1} \rightarrow c{2} \rightarrow \cdots \rightarrow c{l} \rightarrow c{1}(其中对于所有 1 \leq i<l,城市 ci 与城市 c{i+1} 有道路相连;城市 c_l 与城市 c1 有道路相连;对于所有 1 \leq i<j \leq l,有 c{i} \neq c_{j}),若 l > 3$,则 C 国的道路将满足下列条件:

  • 存在两个在该环路上不相邻的城市 u, v,满足两个城市间有道路直接相连。即:存在 1 \leq u,使得 v-u \geq 2uv 不同时为 1l,并且城市 c_u 与城市 c_v 间有道路直接相连。

现在 C 国有了新的翻修计划,需要在城市 s 与城市 t 间寻找一条路径进行翻修。翻修时路径中包含的所有道路将无法通行,为了保障人民的日常生活,C 国希望在翻修这条路径时,经由剩余的道路(即没被包含在翻修路径内的道路)依然能满足:从 C 国中任意一个城市出发,均能到达其他所有城市

C 国找到了身为工程大师的你,请你帮助 C 国找出一条满足上述要求的翻修路径,并使得这条路径的总长尽量小

输入

第一行两个整数 n, m 分别表示城市个数与道路条数。

接下来 m 行每行三个整数 u_i, v_i, w_i,依次表示每条道路的两个端点与它的长度。

数据保证每条道路都一定连接两个不同城市,即 u_i \not= v_i

最后一行两个整数 s, t,分别表示需要翻修的路径的两个端点。

输出

仅一行一个整数,表示满足题目要求的情况下,翻修路径的总长的最小值。

如果不存在满足题目要求的路径,输出一行一个整数-1

样例

输入

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

输出

6

输入

2 1
1 2 1
1 2

输出

-1

提示

样例 1 解释

路径 (1,2,1),(2,3,1),(3,4,1) 是城市 1 和城市 4 间总长最小的路径,但不符合要求。

路径 (1,3,5),(3,4,1) 符合要求,长度为 6

路径 (1,2,1),(2,4,6) 符合要求,长度为 7

除上述两条路径外,没有其他满足要求的路径。

来源

NOI