#include <iostream>#include <stdio.h>#include <string.h>#include <queue>#include <algorithm>#define clr(a,b) memset(a,b,sizeof(a))using namespace std;const int N = 100+10;const int M = 250000+10;const int inf = 0x3f3f3f3f;int n, m, e, t, sh, ans;int he[N], vis[N][N], d[N][N];int ev[M], ew[M], nxt[M], flag[M];struct node{int id, dis, use;node(){};node(int a, int b, int c):id(a),dis(b),use(c){};bool operator < (const node& a)const{ if (use == a.use) return dis > a.dis; return use > a.use;}};void init(){ e = 0; clr(he, -1); clr(flag, 0); ans = inf;}void add(int u, int v, int w){ ev[e]=v; ew[e]=w; nxt[e]=he[u]; he[u]=e++; ev[e]=u; ew[e]=w; nxt[e]=he[v]; he[v]=e++;}void dijkstra(int s, int ed){ priority_queue<node>q; for (int i=0; i<=100; i++) for (int j=0; j<=100; j++) d[i][j] = inf; clr(vis, 0); d[s][0] = 0; q.push(node(s,0,0)); while (!q.empty()) { node tmp = q.top(); q.pop(); int u = tmp.id, h = tmp.use; if (vis[u][h] && u==ed)return; if (vis[u][h]) continue; vis[u][h] = 1; for (int i=he[u]; ~i; i=nxt[i]) { int v = ev[i]; if (flag[i]) { if (d[v][h+1] > d[u][h] + ew[i]) { d[v][h+1] = d[u][h] + ew[i]; if (d[v][h+1]<=t)q.push(node(v,d[v][h+1],h+1)); } } else { if (d[v][h] > d[u][h] + ew[i]) { d[v][h] = d[u][h] + ew[i]; if (d[v][h]<=t)q.push(node(v,d[v][h],h)); } } } }}int main(){ while (~scanf("%d", &n)) { scanf("%d", &m); init(); for (int i=0; i<m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); } scanf("%d", &sh); for (int i=0; i<sh; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); flag[e-1] = flag[e-2] = 1; } int st, ed; scanf("%d%d%d", &st, &ed, &t); dijkstra(st, ed); for (int i=0; i<=100; i++) { if (d[ed][i]<=t) { ans = i;break;} } if (ans == inf) printf("Impossiblen"); else printf("%dn", ans); } return 0;}
