P6777 [NOI2020] 翻修道路【数据有误】

本题官方数据有误。正确的解法见 [Shortest non-separating st-path on chordal graphs](https://arxiv.org/abs/2101.03519)。

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 \leq i

第一行两个整数 $n$, $m$ 分别表示城市个数与道路条数。 接下来 $m$ 行每行三个整数 $u_i$, $v_i$, $w_i$，依次表示每条道路的两个端点与它的长度。 数据保证每条道路都一定连接两个不同城市，即 $u_i \not= v_i$。 最后一行两个整数 $s$, $t$，分别表示需要翻修的路径的两个端点。

仅一行一个整数，表示满足题目要求的情况下，翻修路径的总长的最小值。 **如果不存在满足题目要求的路径，输出一行一个整数$-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$。 除上述两条路径外，没有其他满足要求的路径。 #### 样例 3 见选手目录下的 road/road3.in 与 road/road3.ans。该样例与测试点 $1 \sim 6$ 限制相同。 #### 样例 4 见选手目录下的 road/road4.in 与 road/road4.ans。该样例与测试点 $7 \sim 10$ 限制相同。 #### 样例 5 见选手目录下的 road/road5.in 与 road/road5.ans。该样例与测试点 $11 \sim 15$ 限制相同。 #### 样例 6 见选手目录下的 road/road6.in 与 road/road6.ans。该样例与测试点 $16 \sim 20$ 限制相同。 --- ### 测试点约束 对于所有测试点：$2 \leq n \leq 5 \times 10^{5}$，$2 \leq m \leq 10^{6}$，$s \neq t$。 $1 \leq u_{i}, v_{i} \leq n$，$u_{i} \neq v_{i}$，$1 \leq w_{i} \leq 10^{9}$，保证任意两条道路它们的端点不全相同。 保证给出的道路满足题面描述第二段中的性质。 每个测试点的具体限制见下表： | 测试点编号 | $n\le $ | $m\le $ | 特殊限制 | | :-: | :-: | :-:| :-: | | $1\sim 6$ | $2\times 10^3$ | $4\times 10^3$ | 无 | | $7\sim 10$ | $5\times 10^5$ | $10^6$ | $\text{A}$ | | $11\sim 15$ | $5\times 10^5$ | $10^6$ | $\text{B}$ | | $16\sim 20$ | $5\times 10^5$ | $10^6$ | 无 | 特殊限制 A：所有道路的长度均相等。 特殊限制 B：所有 $w_i = 1$ 的道路恰好构成 $s$ 到 $t$ 的一条路径，且其他 $w_i \not= 1$ 的道路的两条端点在这条路径上距离为 $2$。