P6777 [NOI2020] Road Renovation [Incorrect testdata]

The official testdata of this problem is incorrect. The correct solution can be found in [Shortest non-separating st-path on chordal graphs](https://arxiv.org/abs/2101.03519)。

Country C contains $n$ cities, connected by $m$ undirected roads. The cities are numbered from $1$ to $n$, and the roads are numbered from $1$ to $m$. Road $i$ connects cities $u_i$ and $v_i$, and its length is $w_i$ meters. Using these roads, starting from any city in Country C, one can reach all other cities. People in Country C like traveling along cycles, but they do not like passing through too many roads, so the roads in Country C are built in a very special way. More specifically, for a simple cycle that passes through $l$ roads (i.e. a cycle that visits **no repeated city except the starting city**), it can be written as $c_{1} \rightarrow c_{2} \rightarrow \cdots \rightarrow c_{l} \rightarrow c_{1}$ (where for all $1 \leq i

The first line contains two integers $n$, $m$, representing the number of cities and the number of roads. The next $m$ lines each contain three integers $u_i$, $v_i$, $w_i$, representing the two endpoints of each road and its length. The testdata guarantees that each road connects two different cities, i.e. $u_i \not= v_i$. The last line contains two integers $s$, $t$, representing the two endpoints of the path to be renovated.

Output a single integer in one line, representing the minimum total length of a renovation path that satisfies the requirements. **If there is no path that satisfies the requirements, output one integer $-1$ in one line.**

#### Explanation for Sample 1 The path $(1,2,1),(2,3,1),(3,4,1)$ is the shortest path (by total length) between cities $1$ and $4$, but it does not satisfy the requirement. The path $(1,3,5),(3,4,1)$ satisfies the requirement, with length $6$. The path $(1,2,1),(2,4,6)$ satisfies the requirement, with length $7$. Other than the two paths above, there is no other path that satisfies the requirement. #### Sample 3 See road/road3.in and road/road3.ans in the contestant directory. This sample has the same constraints as test points $1 \sim 6$. #### Sample 4 See road/road4.in and road/road4.ans in the contestant directory. This sample has the same constraints as test points $7 \sim 10$. #### Sample 5 See road/road5.in and road/road5.ans in the contestant directory. This sample has the same constraints as test points $11 \sim 15$. #### Sample 6 See road/road6.in and road/road6.ans in the contestant directory. This sample has the same constraints as test points $16 \sim 20$. --- ### Constraints For all test points: $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}$, and it is guaranteed that for any two roads, their endpoints are not both the same. It is guaranteed that the given roads satisfy the property described in the second paragraph of the statement. The detailed limits for each test point are shown in the table below: | Test Point ID | $n \leq$ | $m \leq$ | Special Constraint | | :-: | :-: | :-: | :-: | | $1 \sim 6$ | $2 \times 10^3$ | $4 \times 10^3$ | None | | $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$ | None | Special constraint A: All roads have the same length. Special constraint B: All roads with $w_i = 1$ form exactly one path from $s$ to $t$, and for every other road with $w_i \not= 1$, the distance between its two endpoints along this path is $2$. Translated by ChatGPT 5