题目描述

一群青少年偷走了一辆跑车兜风。警方只有一辆警车可用于追捕。

城市由若干路口和双向道路组成，每条道路都有一个正长度。青少年停在某个路口，直到警车即将到达该路口。在警车到达前的一瞬间，他们会逃往尽可能远的路口，具体规则如下：

1. 此时警车位于通向青少年当前路口的某条道路上。青少年不能经过警车所在的这条道路。
2. 他们先找出在不经过该道路的前提下，从当前位置仍然可达的所有路口。
3. 对这些可达路口，他们使用导航系统计算与当前位置之间的最短路距离。导航系统并不知道警车的位置，因此计算距离时仍按完整城市道路网计算。
4. 他们在距离最大的路口中随机选择一个，并瞬间沿某条不经过警车的路线到达该路口。
5. 之后，他们继续等待警车下一次接近。

警方只有在青少年位于死胡同，即度数为 $1$ 的路口时，才能在接近过程中将他们抓获。

警方希望采用最优策略，并且必须无论青少年每次在最远路口中怎样随机选择，都能保证抓获他们。

请判断警方是否能够必然抓获青少年。若可以，求为了保证抓获，警车最少需要行驶的总距离。

输入格式

第一行包含四个整数 $n,m,p,t$：

• $n$：路口数量；
• $m$：道路数量；
• $p$：警车的初始路口；
• $t$：青少年的初始路口。

接下来 $m$ 行，每行包含三个整数 $a,b,\ell$，表示路口 $a$ 与路口 $b$ 之间有一条长度为 $\ell$ 的双向道路。

任意两个路口之间至多有一条道路，且整个图连通。

输出格式

若警方可以保证抓获青少年，输出警车在最优策略下所需行驶的最小总距离。

否则输出：

impossible

数据范围

样例过程示意

样例 1 中警车与青少年的移动过程

实线蓝色箭头表示警车的移动，其耗时/代价等于道路长度；虚线红色箭头表示青少年的瞬间移动。

样例 1

输入

5 5 1 2
1 2 2
2 3 2
3 4 3
4 5 1
2 5 2

输出

10

样例 2

输入

5 5 1 3
1 2 2
2 3 2
3 4 3
4 5 1
2 5 2

输出

impossible