题目描述

$\red{JY}$是一个爱旅游的探险家，也是一名强迫症患者。现在$\red{JY}$想要在$\red{C}$国进行一次长途旅行，$\red{C}$国拥有$\red{n}$个城市(编号为$\red{0,1,2...,n - 1)，}$城市之间有$\red{m}$条道路，可能某个城市到自己有一条道路，也有可能两个城市之间有多条道路，通过每条道路都要花费一些时间。$\red{JY}$从$\red{0}$号城市开始出发，目的地为$\red{n - 1}$号城市。由于$\red{JY}$想要好好参观一下$\red{C}$国，所以$\red{JY}$想要旅行恰好$\red{T}$小时。为了让自己的旅行更有意思，$\red{JY}$决定不在任何一个时刻停留(走一条到城市自己的路并不算停留)。$\red{JY}$想知道 是否能够花恰好$\red{T}$小时到达$\red{n - 1}$号城市（每个城市可经过多次）。现在这个问题交给了你。

若可以恰好到达输出"$\red{Possible}$"否则输出"$\red{Impossible}$"。$\red{(}$不含引号$\red{)}$。

输入格式

第一行一个正整数$\red{Case，}$表示数据组数。

每组数据第一行$\red{3}$个整数，分别为$\red{n, m, T}$。

接下来$\red{m}$行，每行$\red{3}$个整数$\red{x, y, z,}$代表城市$\red{x}$和城市$\red{y}$之间有一条耗时为$\red{z}$的双向边。

输出格式

对于每组数据输出"$\red{Possible}$"或者"$\red{Impossible}$".

样例

输入样例

2
3 3 11
0 2 7
0 1 6
1 2 5
2 1 10000
1 0 1

输出样例

Possible
Impossible

提示

样例解释

第一组：$\red{0 -> 1 -> 2 :11}$

第二组：显然偶数时间都是不可能的。

数据范围

$\red{30\%: T <= 10000 }$

另有$\red{30\%: n <= 5 , m <= 10.}$

$\red{100\%: 2 <= n <= 50 , 1 <= m <= 100 , 1 <= z <= 10000 , 1 <= T <= 10^{18} , Case <= 5.}$