시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 57 12 6 21.429%

문제

두 개의 도시와 N(0≤N≤150)개의 마을로 이루어진 나라가 있다. 몇 개의 마을과 도시 사이에는 양방향으로 이동 가능한 길이 있기도 하다. 각각의 길을 이용하여 이동하는데 걸리는 시간은 서로 다를 수 있지만, 하나의 길을 이동할 때에는 어느 방향으로 이동해도 같은 시간이 걸린다.

이 나라에서는 치안에 신경을 쓰기 위해 군대를 배치하기로 하였다. 군대를 마을에 배치할 경우에는 마을 사람들에게 불편을 끼칠 우려가 있기 때문에, 군대를 배치할 때에는 반드시 길 위에 배치해야 한다. 길 위에 배치할 때에는 그 길이 연결하는 두 개의 마을(혹은 도시) 중 어느 한쪽에 원하는 만큼 가까이 배치할 수 있다.

이 나라의 군대는 G(0≤G≤353535)명의 군인으로 구성되어 있는데, 한 곳에 모든 군인을 배치할 수도 있고, 서로 다른 길에 군인들을 배치할 수도 있으며, 한 길 위에도 여러 명의 군인을 (서로 다른 위치에) 배치할 수도 있다. 단, 이와 같이 군대를 배치했을 때, 두 도시 사이를 이동하기 위해서는 적어도 한 명의 군인과 반드시 마주치도록 배치해야 한다.

또한 때로는 각 도시로 군대를 소집해야 할 필요가 있을 수도 있다. 군대를 소집하는 것은 두 도시 중 어느 한 쪽에서도 할 수 있으며, 군대를 소집하는데 걸리는 시간은 제일 마지막 군인이 마을에 도착하는 시간이 된다. 나라에서는 군대를 효율적으로 배치하기 위해서, 두 도시에서 군대를 소집하는데 걸리는 시간 중 더 큰 값이 작아지도록 하려 한다.

도시와 마을에 대한 정보가 주어졌을 때, 군대를 소집하는데 걸리는 시간의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N, G, E(0≤E≤5,000)가 주어진다. 다음 E개의 줄에는 각 길에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 마을(혹은 도시)와 B번 마을(혹은 도시) 사이에 C만큼 시간이 걸리는 길이 있음을 의미한다. 마을의 번호는 0부터 N-1까지의 정수로 표현되며, 두 도시는 각각 95050과 104729로 표현된다.

출력

첫째 줄에 답을 출력한다. 답을 출력할 때에는 소수점 아래 첫째 자리까지(둘째 자리에서 반올림) 출력한다. 위의 조건을 만족하도록 군대를 배치하는 것이 불가능한 경우에는 Impossible을 출력한다.

예제 입력

4 2 6
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1

예제 출력

2.5

힌트