【题目描述】

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

【输入格式】

第一行一个正整数 Case，表示数据组数。 每组数据第一行 3 个整数，分别为 n, m, T。 接下来 m 行，每行 3 个整数 x, y, z,代表城市 x 和城市 y 之间有一条耗时为 z 的双向边。

【输出格式】

对于每组数据输出”Possible”或者”Impossible”.

【样例输入】

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

【样例输出】

Possible
Impossible

【样例解释】

第一组：0 -> 1 -> 2 :11 第二组：显然偶数时间都是不可能的。

【数据范围】

30%: T <= 10000

另有 30%: n <= 5 , m <= 10.

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