GS국은 수원시에 떠있는 작은 산나라이다.

GS국에는 N개의 섬이 있고, 1부터 N까지의 번호가 붙어 있다.

GS국은 섬끼리 주로 무선통신을 한다.

각 섬에는 전파의 발신기와 수신기가 하나씩 있다.

발신기는 모든 방향으로 전파를 발신하는 것이 가능하지만, 수신기는 특정 방향에서 오는 전파밖에 받지 못한다.

다시 말해, 수신기는 특정 하나의 섬에서만 전파를 수신할 수 있다.

단, 수신기의 방향을 바꾸는 것으로, 어느 섬에서 전파를 수신할 것인지 바꿀 수는 있다.

GS국에서는 공공사업으로 전보 서비스를 한다.

섬 i(1 ≤ i ≤ N)에서 전파를 섬 j(1 ≤ j ≤ N, j ≠ i)의 수신기가 받는 것이 가능할 때,

섬 i에서 섬 j로 전보를 보내는 것이 가능하다.

또한, 전보는 몇 개의 섬을 경유할 수 있다.

즉, 섬 i, 섬 j, 섬 k에 대해, 섬 i에서 섬 j에 전보를 보낼 수 있고,

섬 j에서 섬 k에 전보를 보낼 수 있으면, 섬 i에서 섬 k에 전보를 보낼 수도 있다.

GS국의 통신장관인 준혁이는 임의의 섬에서 임의의 섬으로 전보를 보낼 수 있도록 하고 싶다.

그러기 위해서는 몇 개의 섬의 수신기의 방향을 바꿔야 할 수도 있다.

몇개의 섬의 수신기의 방향을 바꾸는 데 드는 비용은,

각각의 수신기의 방향을 바꾸는 데 사용하는 비용의 총합이다.

여러분이 불쌍한 준혁이를 도와, GS국의 섬의 수와 각각의 섬의 수신기에 대한 정보가 주어졌을 때,

임의의 섬에서 임의의 섬으로 전보를 보낼 수 있도록 하기 위해 드는 비용의 최소치를 구해주자.

통신비용 timer 1s memory 256MB

통신비용 1s 256MB