#6075. 「2017 山东一轮集训 Day6」重建
说明
给定一个 n n n 个点 m m m 条边的带权无向连通图 G G G，以及一个大小为 k k k 的关键点集合 A A A。有个人要从点 s s s 走到点 t t t，现在可以对所有边加上一个非负整数 c c c，问最大的 c c c，使得加上 c c c 后，满足：s s s 到 t t t 的最短路长度 =s = s =s 到 t t t 且只能经过 A A A 中的点的最短路长度。
输入格式
第一行一个整数 T T T。代表这个数据点中有 T T T 个测试数据。
对于每个测试数据：
第一行包含四个整数 n,m,s,t n, m, s, t n,m,s,t。
接下来 m m m 行，每行三个整数 ui,vi,ci u_i, v_i, c_i ui,vi,ci，代表 G G G 中有一条 ui u_i ui 到 vi v_i vi 的长度为 ci c_i ci 的无向边。
第 m+1 m + 1 m+1 行包含一个整数 k k k。
接下来一行 k k k 个整数，代表关键点集合 A A A。保证 s s s 与 t t t 都在 A A A 中。
输出格式
对于每个测试数据，输出一行一个整数 c c c，代表最大的合法的加到每条边的权值。假如不存在这样的合法的 c c c，则输出 Impossible，假如这样的 c c c 可以无穷大，则输出 Infinity。
样例
3
6 8 1 6
1 2 5
1 3 1
2 6 6
2 3 6
4 2 3
3 4 1
4 5 1
5 6 1
5
1 3 6 5 4
3 4 1 2
1 2 6
1 3 2
1 2 7
2 3 3
2
1 2
4 4 1 4
1 2 1
1 3 1
2 4 1
3 4 1
3
1 2 43
Infinity
Infinity提示
对于 20% 20\% 20% 的数据，n,m,ci≤100 n, m, c_i \leq 100 n,m,ci≤100；
对于 40% 40\% 40% 的数据，n,m≤100 n, m \leq 100 n,m≤100；
另外有 20% 20\% 20% 的数据，每个测试数据的答案要么为 Infinity，要么为 Impossible；
对于 100% 100\% 100% 的数据，满足 1≤n≤1000,1≤m≤10000,1≤ci≤109,1≤T≤3 1 \leq n \leq 1000, 1 \leq m \leq 10000, 1 \leq c_i \leq 10 ^ 9, 1 \leq T \leq 3 1≤n≤1000,1≤m≤10000,1≤ci≤109,1≤T≤3。