석표는 N개의 정거장이 있는 도시에 살고 있고,

이 도시에는 M개의 철로들이 두 도시 Ai, Bi를 연결하고 있으며, 이 노선의 요금은 Ci원이다.

석표의 집은 S번 정거장이고, T번 정거장에 있는 학교에 가려고 할 때, 통행권을 하나 구매하려고 한다.

이 통행권을 사용하면 S와 T사이의 최단경로를 하나 고른 후, 그 경로에 속하는 모든 노선을 무료로 이용할 수 있다.

독서를 좋아하는 석표는 정거장 U와 정거장 V 근처에 있는 서점을 방문하려고 한다.

석표가 U와 V사이의 어떤 경로를 따라 이동할 때 낼 돈은, 통행권에 포함되지 않은 노선들에 대한 비용의 합이다.

석표를 도와 할인권을 적당히 잘 구매하였을 때 U에서 V로 이동하는 최단 비용을 계산하여라.

Subtask 1 (16점) : S=U

Subtask 2 (15점) : S에서 T로 가는 유일한 경로가 존재한다.

Subtask 3 (24점) : N<=300

Subtask 4 (45점) : 추가 제한 조건 없음

2 ≤ N ≤ 100 000.

1 ≤ M ≤ 200 000.

1 ≤ S ≤ N.

1 ≤ T ≤ N.

1 ≤ U ≤ N.

1 ≤ V ≤ N.

S ≠ T.

U ≠ V.

S ≠ U 또는 T ≠ V.

어떤 정거장에서 다른 정거장으로 노선들만을 따라서 이동할 수 있다.

1 ≤ Ai < Bi ≤ N (1 ≤ i ≤ M).

모든 1 ≤ i < j ≤ M 에 대하여 Ai ≠ Aj 이거나 Bi ≠ Bj.

1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ M).

통행권 구매 timer 2s memory 256MB

통행권 구매 2s 256MB