동방 택배는 \(N\)개의 도시와 \(M\)개의 양방향 도로로 이루어진 물류망을 운영한다. 각 도로 \(i\)는 도시 \(u_i\)와 \(v_i\)를 잇고, 트럭이 그 도로를 지나는 데 \(w_i\)분이 걸린다.

본사가 있는 도시 \(S\)에서 출발한 트럭이 물류 창고가 있는 도시 \(T\)까지 이동하는 데 걸리는 최소 시간을 구하여라.

도로망은 연결되어 있지 않을 수도 있다. \(S\)에서 \(T\)로 갈 수 없으면 \(-1\)을 출력한다.

같은 두 도시를 잇는 도로가 여러 개 있을 수 있으며(다중 간선), 이때는 가장 빠른 도로를 쓰면 된다. 자기 자신으로 돌아오는 도로(자기 루프)는 주어지지 않는다.

• \(2 \le N \le 20{,}000\)
• \(1 \le M \le 100{,}000\)
• \(1 \le u_i, v_i \le N\), \(u_i \ne v_i\)
• \(1 \le w_i \le 10{,}000\)
• \(1 \le S, T \le N\), \(S \ne T\)

첫째 줄에 도시의 수 \(N\), 도로의 수 \(M\), 출발 도시 \(S\), 도착 도시 \(T\)가 공백으로 구분되어 주어진다.

다음 \(M\)개의 줄에 각각 \(u_i\ v_i\ w_i\)가 주어진다 — 도시 \(u_i\)와 \(v_i\)를 잇는 도로의 소요 시간이 \(w_i\)분이라는 뜻이다.

\(S\)에서 \(T\)까지의 최소 이동 시간을 한 줄에 출력한다. 도달할 수 없으면 \(-1\)을 출력한다.

riseoj 작성

출처 Original