1831 - 不在场的证明
描述

农场有 FF 个点,已知 PP 条边以及每条边的起点终点和通过时间,给出 CC 个有牛的点,求在规定时间 MM 内能从起点到达牛当前位置的牛的数量,并按升序输出牛的编号。

谷仓里发现谷物被盗!FJ 正试图从 CC 只奶牛里找出那个偷谷物的罪犯。幸运的是,一个恰好路过的卫星拍下谷物被盗前 MM 秒的农场的图片。这样约翰就能通过牛们的位置来判断谁有足够的时间来盗窃谷物。

约翰农场有 FF 草地,标号 11FF,还有 PP 条双向路连接着它们。通过这些路需要的时间在 117000070000 秒的范围内。田地 11 上建有那个被盗的谷仓。给出农场地图,以及卫星照片里每只牛所在的位置,请判断哪些牛有可能犯罪。

请注意:数据里可能存在重边(起点和终点相同的边)。


输入

11 行:四个以空格分隔的整数:F,P,CF,P,CMM

22 行至 P+1P+1 行:三个空间分隔的整数,描述一个路径。连接 F1F1F2F2 的路径需要 TT 秒。

P+2P+2 行至 P+C+1P+C+1 行:每行一个整数,是一头牛的位置。


输出

11 行输出嫌疑犯的数目,接下来每一行输出一只嫌疑犯的编号。

样例

输入
复制

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

输出
复制

4
1
2
3
4
提示

对于 100%100\% 的数据:1M700001 \le M \le 700001C1001 \le C \le 1001P10001 \le P \le 10001F5001 \le F \le 500

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 41
通过次数 14