【题目描述】
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 ='0'&&ch'9'){if(ch=='-')f=-1;ch = getchar();}while(ch>='0'&&ch dd){dist[to][nmod] = dd;if(!vis[to][nmod]){vis[to][nmod] = true;tmp.d = nmod;tmp.u = to;q.push(tmp);}}}}}int main(){freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);int T = read();edge tmp;while(T--){n = read();m = read();t = Read();md = inf;for(int i = 1;i w && (!u||!v)) md = w;}md*=2;spfa();if(dist[n-1][t%md]