题目描述

C 国中包含 $n$ 座城市，这些城市通过 $m$ 条双向道路连接。城市从 $1$ 到 $n$ 编号，道路从 $1$ 到 $m$ 编号，$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\le i < l$，城市 $c_i$ 与城市 $c_{i+1}$ 有道路相连；城市 $c_l$ 与城市 $c_1$ 有道路相连；对于所有 $1\le i < j\le l$，有 $c_i \neq c_j$），若 $l > 3$，则 C 国的道路将满足下列条件：

• 存在两个在该环路上不相邻的城市 $u, v$，满足两个城市间有道路直接相连。即：存在 $1\le u < v\le l$，使得 $v - u \ge 2$，$u$ 和 $v$ 不同时为 $1$ 和 $l$，并且城市 $c_u$ 与城市 $c_v$ 间有道路直接相连。

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

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

输入格式

从文件 road.in 中读入数据。

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

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

数据保证每条道路都一定连接两个不同城市，即 $u_i \neq v_i$。

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

输出格式

输出到文件 road.out 中。

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

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

样例

样例输入 1

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

样例输出 1

6

样例解释 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$。

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

样例解释 2

2 1
1 2 1
1 2

样例输出 2

-1

样例 3

见下发文件中的 road3.in 与 road3.ans。

该样例与测试点 $1\sim 6$ 相同。

样例 4

见下发文件中的 road4.in 与 road4.ans。

该样例与测试点 $7\sim 10$ 相同。

样例 5

见下发文件中的 road5.in 与 road5.ans。

该样例与测试点 $11\sim 15$ 相同。

样例 6

见下发文件中的 road6.in 与 road6.ans。

该样例与测试点 $16\sim 20$ 相同。

数据范围与提示

对于所有测试点：$2\le n\le 5\times 10^5$，$2\le m\le 10^6$，$s \neq t$。

$1\le u_i, v_i\le n$，$u_i \neq v_i$，$1\le w_i\le 10^9$，保证任意两条道路它们的端点不全相同。

保证给出的道路满足题面描述第二段中的性质。

每个测试点的具体限制见下表：

测试点编号	$n\le$	$m\le$	特殊限制
$1\sim6$	$2000$	$4000$
$7\sim10$	$5\times 10^5$	$10^6$	A
$11\sim15$			B
$16\sim20$

特殊限制 A：所有道路的长度均相等。

特殊限制 B：所有 $w_i = 1$ 的道路恰好构成 $s$ 到 $t$ 的一条路径，且其他 $w_i \neq 1$ 的道路的两条端点在这条路径上距离为 $2$。