도로

나라에 $n$개의 도시가 있고, 이 도시들은 양방향 도로 $m$개로 연결되어 있다. 도시는 $1, 2, \dots, n$, 도로는 $1, 2, \dots, m$으로 번호가 매겨져 있다. $i$번 도로는 도시 $u_i$와 도시 $v_i$를 잇고, 길이는 $w_i$미터이다. 어느 도시에서 출발하든 도로를 따라 다른 모든 도시에 갈 수 있다.

도로는 특별한 방식으로 지어져 있다. 정확히 말하면, $l$개의 도로를 지나는 단순 사이클(시작점을 제외하고 같은 도시를 두 번 방문하지 않는 사이클)은 $c_1 \to c_2 \to \dots \to c_{l-1} \to c_l$로 나타낼 수 있다. 이때 모든 $1 \le i < l$에 대해 도시 $c_i$와 $c_{i+1}$은 도로로 직접 연결되어 있고, 도시 $c_1$과 $c_l$도 도로로 직접 연결되어 있으며, 모든 $1 \le i < j \le l$에 대해 $c_i \ne c_j$이다. $l > 3$이면 도로는 다음 조건도 만족해야 한다. 사이클 위에 서로 인접하지 않은 두 도시가 있고, 두 도시가 도로로 직접 연결되어 있다. 즉 $1 \le u < v \le l$, $v-u \ge 2$이며, $u$와 $v$가 동시에 $1$과 $l$이 아니고, 도시 $c_u$와 $c_v$가 도로로 직접 연결되는 $u, v$가 존재한다.

나라가 도시 $s$와 도시 $t$ 사이의 경로를 보수하려고 한다. 보수하는 동안 그 경로는 막히므로, 남은 도로만으로 어느 도시에서 출발하든 다른 모든 도시에 도달할 수 있어야 한다. 가능한 보수 경로 중 총 길이가 가장 짧은 것을 찾아라.

첫째 줄에 도시의 수 $n$과 도로의 수 $m$이 주어진다. 이어지는 $m$개의 줄에는 세 정수 $u_i$, $v_i$, $w_i$가 각각 주어지며, 이는 $i$번 도로의 양 끝 도시와 길이이다. 각 도로는 서로 다른 두 도시를 잇는다. 마지막 줄에는 보수할 경로의 양 끝점 $s$와 $t$가 주어진다.

조건을 만족하는 보수 경로의 최소 길이를 정수 하나로 출력한다. 가능한 경로가 없으면 $-1$을 출력한다.

모든 테스트 케이스에 대해 $2 \le n \le 5 \times 10^5$, $2 \le m \le 10^6$, $s \ne t$, $1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le w_i \le 10^9$이다. 두 도로의 양 끝점이 완전히 같은 경우는 없다. 도로는 문제에서 설명한 조건을 만족하도록 주어진다.