Jan Ersa

Gustaf Fröding의 시는 이렇게 시작한다:

*Jan Ersa는 Nackabyn을 소유했고,

Per Persa는 Backabyn을 소유했다

Västra Ed의 By에서.

Jan Ersa,

Per Persa,

그들은 결코 화목하게 지내지 않았다.*

Jan Ersa와 Per Persa는 나이가 들어 도시로 이사했을 때, 서로 가능한 한 멀리 떨어진 곳에 살도록 했다. 도시의 도로 정보를 입력받은 뒤, 최단 경로가 가장 긴 두 집을 구하고 그 경로의 길이를 답하는 프로그램을 작성한다.

[ht!]

지도는 예제에 나오는 도시의 모든 집과 도로를 보여 준다. 또한 현재 Jan Ersa와 Per Persa가 사는 빨간색 집도 볼 수 있다. 이 두 집(번호 1과 9)은 도시에서 서로 가장 멀리 떨어진 집이며, 그 거리는 4900미터이다.

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$30$| $N \leq 25$

$2$ |$70$| 추가 제한이 없다.

첫째 줄에는 도시의 집 수를 나타내는 수 $N$ ($2 \le N \le 100$)가 주어진다. 집에는 $1$부터 $N$까지 번호가 매겨져 있다. 다음 줄에는 도로의 수를 나타내는 수 $V$이 주어지며, $2 \le V \le 500$이다. 이어지는 $V$개의 줄에는 각 줄마다 출발 집 번호, 도착 집 번호, 도로의 길이라는 세 수가 주어진다. 도로의 길이는 100미터 단위로 주어진다. 주어진 입력에서는 항상 어떤 집에서든 다른 어떤 집으로든 이동할 수 있다.

서로 가장 멀리 떨어진 두 집 사이의 거리를 미터 단위로 출력한다.