프라하 연결선

경찰에게는 현재 상황을 정확히 아는 일이 중요하다. 통신선이 고장 나면 초소 사이의 연락이 끊기고, 그때는 전령이 대신 소식을 나른다. 전령 한 명은 정해진 장소에서 정해진 시각에 소식을 전할 수 있다. 전령이 자전거를 타고 다녀도 소식을 옮길 거리를 미리 아는 일은 여전히 중요하다. 그래서 전령은 목적지에 가장 빨리 닿도록 언제나 최단 경로를 고른다. 소요 때문에 일부 도로를 쓰지 못할 때도 있고, 심하면 초소 전체가 서로 연락이 닿지 않는 두 무리 이상으로 갈라진다.

경찰은 초소의 배치와 초소 사이의 거리를 빠짐없이 기록해 둔다. 그래서 초소 사이의 거리를 모두 조사해 전령에게 가장 불리한 경로를 찾아낼 수 있다. 그 값으로 위기 상황의 보고가 얼마나 최신 상태를 유지할지 가늠한다.

첫 줄에 테스트 케이스의 개수인 양의 정수 Z가 주어진다. 이어서 Z개의 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫 줄에는 초소의 개수 J와 초소를 잇는 연결선의 개수 S가 공백을 사이에 두고 주어진다 ($2 \le J \le 300$, $0 \le S \le J(J-1)/2$). 다음 S개의 줄에는 각각 정수 세 개가 공백을 사이에 두고 주어진다. 앞의 두 수는 연결선이 잇는 두 초소의 번호이고, 초소에는 1번부터 J번까지 번호가 붙어 있다. 세 번째 수는 그 연결선의 길이이며 양의 정수다.

두 초소를 직접 잇는 연결선보다 다른 초소를 거쳐 가는 길이 더 짧을 수도 있다. 전령은 그런 길도 쓸 수 있다. 한 테스트 케이스 안에서 같은 초소 쌍이 두 번 주어지는 일은 없다.

테스트 케이스마다 한 줄씩 출력한다.

모든 초소 쌍의 최단 거리 가운데 가장 큰 값을 V라고 하면 Nejvetsi vzdalenost je V.를 출력한다. V 자리에는 그 값을 적는다. 경로는 주어진 연결선만 따라간다.

서로 오갈 수 있는 길이 아예 없는 초소 쌍이 하나라도 있으면 대신 Bez spojeni neni veleni!를 출력한다.