군사 배치

두 도시와 N개의 마을이 있는 나라가 있다. 일부 마을과 도시는 양방향 도로로 연결되어 있으며, 도로마다 이동 시간이 다를 수 있다. 한 도로를 지나는 데 걸리는 시간은 어느 방향으로 이동해도 같다.

이 나라는 치안을 위해 G명의 군인을 배치하려고 한다. 군인은 마을이나 도시에 둘 수 없고 반드시 도로 위에 배치해야 한다. 도로 위라면 그 도로가 잇는 두 끝점 중 어느 한쪽에 원하는 만큼 가깝게 배치할 수 있다. 모든 군인을 한 곳에 둘 수도 있고 여러 도로에 나누어 둘 수도 있으며, 같은 도로 위에 여러 명을 둘 수도 있다.

배치가 끝난 뒤에는 두 도시 사이를 이동하는 어떤 경로도 적어도 한 명의 군인을 지나야 한다.

나중에 두 도시 중 어느 한 도시로 군대를 소집할 수 있다. 한 도시로 소집하는 데 걸리는 시간은 배치된 군인들 중 가장 늦게 그 도시에 도착하는 군인의 도착 시간이다. 두 도시 각각에서 소집하는 데 걸리는 시간 중 더 큰 값이 최소가 되도록 군인을 배치하려고 한다.

도시와 마을, 도로 정보가 주어질 때 가능한 최소 시간을 구하시오.

첫째 줄에 세 정수 N, G, E가 주어진다. 여기서 0 <= N <= 150, 0 <= G <= 353535, 0 <= E <= 5000이다.

다음 E개의 줄에는 도로 하나를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 마을 또는 도시와 B번 마을 또는 도시 사이를 잇는 양방향 도로를 지나는 데 C만큼 시간이 걸린다는 뜻이다.

마을 번호는 0부터 N - 1까지의 정수이다. 두 도시는 각각 95050과 104729로 주어진다. C는 1 이상 1000 이하의 정수이다.

조건을 만족하는 배치 중, 두 도시 각각에서 배치된 모든 군인을 소집하는 데 걸리는 시간의 최댓값이 최소가 되도록 한다. 그 최솟값을 소수점 아래 첫째 자리까지 출력한다. 소수점 둘째 자리에서 반올림한다.

조건을 만족하는 배치가 불가능하면 Impossible을 출력한다.