\(N\)개의 도시가 있고 도시들 사이에 \(M\)개의 단방향 통신로가 있다. \(i\)번째 통신로는 도시 \(u_i\)에서 도시 \(v_i\)로 향하며, 이 통신로를 가동하는 데 \(w_i\)의 비용이 든다.

왕은 도시 \(R\)에 산다. 왕은 자신의 명령이 도시 \(R\)에서 출발하여 선택된 통신로만을 따라 모든 도시에 도달할 수 있도록 통신로의 부분집합을 선택하려 한다. 단, 도시 \(R\)을 제외한 모든 도시는 선택된 통신로 중 정확히 하나의 들어오는 통신로를 가져야 한다.

이러한 조건을 만족하도록 통신로를 선택할 때 드는 가동 비용의 합의 최솟값을 구하여라. 만약 어떤 방법으로도 모든 도시에 명령을 전달할 수 없다면 \(-1\)을 출력하여라.

\(1 \le N \le 1{,}000\)

\(0 \le M \le 100{,}000\)

\(1 \le R \le N\)

\(1 \le u_i, v_i \le N\)

\(0 \le w_i \le 10^9\)

같은 두 도시 사이에 여러 통신로가 있을 수 있고, 자기 자신으로 향하는 통신로도 있을 수 있다.

첫 줄에 도시의 수 \(N\), 통신로의 수 \(M\), 왕이 사는 도시 \(R\)이 주어진다.

이어서 \(M\)개의 줄에 각 통신로의 \(u_i\), \(v_i\), \(w_i\)가 주어진다. (\(u_i\)에서 \(v_i\)로 향하는 단방향 통신로이며 가동 비용은 \(w_i\)이다.)

조건을 만족하는 최소 가동 비용을 출력한다. 불가능하면 \(-1\)을 출력한다.

riseoj 작성

출처 Original