세 로봇

무방향 가중치 그래프 G가 주어지고, G는 연결 그래프이다. 즉, G의 임의의 두 정점은 경로로 연결된다. 세 로봇이 간선을 따라 G를 탐사한다. 여기서 각 간선의 가중치는 로봇이 그 간선을 지날 때 걸리는 시간을 뜻한다. 모든 로봇의 이동 속도는 같고, 두 대 이상의 로봇이 동시에 같은 간선을 지날 수 있다. 로봇들의 탐사 도중 어느 순간에 세 로봇 모두 한 정점에서 만나 정보를 공유해야 하는데, 이를 랑데부라고 한다.

처음에 세 로봇은 지정된 정점에 있다. 물론 두 대 이상의 로봇이 같은 정점에 있을 수도 있다. 또한 세 로봇은 모두 동시에 움직이기 시작한다. 첫 번째 랑데부를 이루는 데 필요한 최소 시간을 구하고자 한다.

그림 L.1

예를 들어 그림 L.1에서 처음에 세 로봇이 정점 1, 5, 7에 있다고 하자. 정점 1에 있는 로봇이 정점 9로 이동하는 데는 최소 9 시간 단위가 필요하다. 또한 정점 5와 정점 7에 있는 로봇이 정점 9로 이동하는 데는 각각 최소 8, 3 시간 단위가 필요하다. 따라서 정점 9에서의 랑데부는 최소 9 시간 단위가 필요하고, 이것이 첫 번째 랑데부에 필요한 최소 시간이다. 물론 첫 번째 랑데부는 정점 1이나 4에서 일어날 수도 있고, 이 경우에도 최소 시간 9가 필요하다.

가중치가 있는 연결 그래프 G와 세 로봇의 초기 위치가 주어질 때, 첫 번째 랑데부를 이루는 데 필요한 최소 시간을 구하는 프로그램을 작성하시오.

프로그램은 표준 입력에서 입력을 읽는다. 입력의 첫 줄에는 두 정수 N과 M (1 ≤ N ≤ 20,000, N − 1 ≤ M ≤ 100,000)이 주어지는데, N과 M은 각각 G의 정점 수와 간선 수이다. G의 정점은 1, 2, … , N으로 표현된다. 다음 M개의 줄 각각에는 세 정수 a, b, t (1 ≤ a ≠ b ≤ N, 1 ≤ t ≤ 10,000)가 주어지는데, 간선이 두 정점 a와 b를 연결하고 그 가중치가 t임을 뜻한다. 마지막 (M + 2)번째 줄에는 세 정수 u, v, w가 주어지는데, 이는 세 로봇의 초기 위치이다 (1 ≤ u, v, w ≤ N). 물론 세 로봇 중 두 대 이상이 처음에 같은 정점에 있을 수도 있다.

프로그램은 표준 출력에 출력한다. 첫 번째 랑데부를 이루는 데 필요한 최소 시간을 한 줄에 정확히 하나만 출력한다.