감옥이냐 질주냐

십대 무리가 토요일 밤에 질주하려고 빠른 스포츠카를 훔쳤다. 지역 경찰서에는 이들을 현장에서 붙잡아 소년원에 보낼 차가 한 대뿐이다.

도시는 교차점과 양방향 도로로 이루어져 있고, 각 도로에는 길이가 정해져 있다. 십대들은 경찰차가 자신들이 있는 교차점에 도착하기 직전까지 그 교차점에 머문다. 바로 그때 십대들은 경찰차가 있는 도로를 이용하지 않고 현재 위치에서 최대한 멀리 떨어진 교차점으로 가려고 한다. 이들은 지도를 재빨리 살펴 경찰차가 있는 도로를 이용하지 않고 도달할 수 있는 도시의 모든 교차점을 찾는다. 그다음 내비게이션으로 이 교차점 각각까지의 거리를 구하고 가장 먼 교차점 중 하나를 무작위로 고른다. 내비게이션은 경찰차의 위치를 알지 못하므로 거리를 계산할 때 경찰차의 위치를 고려하지 않는다. 그러면 스포츠카는 경찰차가 있는 곳을 지나지 않는 임의의 경로로 그 교차점까지 즉시 이동하고 경찰은 어리둥절한 채 뒤에 남는다. 십대들은 경찰차가 다시 접근할 때까지 그곳에서 기다린다. 경찰이 십대들을 붙잡을 수 있는 유일한 방법은 그들이 막다른 길, 즉 연결된 도로가 하나뿐인 교차점에 있을 때 다가가는 것이다. 그림 J.1은 첫 번째 예제에서 경찰이 십대들을 붙잡을 수 있는 방법을 보여 준다.

그림 J.1: 첫 번째 예제에서 경찰(P)과 십대들(T)의 가능한 이동. 경찰의 이동(실선 파란 화살표)은 도로 길이에 따라 시간이 걸리며 십대들의 이동(점선 빨간 화살표)은 즉시 이루어진다.

경찰에게 시간은 중요하므로 당신은 십대들을 확실하게 붙잡을 수 있는지 판별해야 한다. 가능하다면 경찰이 최적의 전략을 사용할 때 십대들을 반드시 붙잡기 위해 경찰차가 주행해야 하는 최소 거리를 구하라.

입력은 다음과 같다.

• 한 줄에 네 정수 $n$ ($2 \leq n \leq 300$), $m$ ($1 \leq m \leq \frac{n(n-1)}{2}$), $p$ ($1 \leq p \leq n$), $t$ ($1 \leq t \leq n$, $t \neq p$)가 주어진다. $n$은 교차점의 수, $m$은 도로의 수, $p$는 경찰차의 초기 위치, $t$는 십대 무리의 초기 위치다.
• 이어서 $m$개의 줄이 주어지고, 각 줄에는 세 정수 $a$, $b$, $\ell$ ($1 \leq a, b \leq n$, $a \neq b$, $1 \leq \ell \leq 10^9$)이 주어진다. 이는 교차점 $a$와 $b$를 잇는 길이 $\ell$인 도로를 나타낸다.

모든 교차점 쌍 사이에는 도로가 최대 하나만 있으며, 도로를 이용해 어떤 교차점에서든 다른 교차점으로 이동할 수 있다.

십대들을 반드시 붙잡을 수 있다면 이를 달성하기 위해 경찰차가 주행해야 하는 최소 거리를 출력한다. 그렇지 않으면 impossible을 출력한다.