时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
竭泽打算乘车去滑稽家拜年。
城市中共有 n 个车站编号从 1 ~ n，竭泽家附近有 n1 个车站可以作为起点，滑稽家附近有 n2 个车站可以作为终点。车站之间有 m 条单向通行的公交线路，可以从一个车站出发抵达另一个车站，搭乘每条线路会有一定的花费。
竭泽预先计算好了抵达滑稽家的最小花费，他只带了恰好够最小花费的钱上了路，并带了 k 件礼物。
因为这座城市中所有的车站都是竭泽的朋友开的，所以竭泽每抵达一个车站时，如果他身上还有礼物则必须留下一件礼物，如果竭泽抵达滑稽家时身上已经没有礼物了，滑稽就不会给他开门并发朋友圈说"we break up"。求竭泽抵达滑稽家时身上最多还剩多少件礼物，如果无法抵达滑稽家，或者已经没有礼物了则输出we break up
城市中共有 n 个车站编号从 1 ~ n，竭泽家附近有 n1 个车站可以作为起点，滑稽家附近有 n2 个车站可以作为终点。车站之间有 m 条单向通行的公交线路，可以从一个车站出发抵达另一个车站，搭乘每条线路会有一定的花费。
竭泽预先计算好了抵达滑稽家的最小花费，他只带了恰好够最小花费的钱上了路，并带了 k 件礼物。
因为这座城市中所有的车站都是竭泽的朋友开的，所以竭泽每抵达一个车站时，如果他身上还有礼物则必须留下一件礼物，如果竭泽抵达滑稽家时身上已经没有礼物了，滑稽就不会给他开门并发朋友圈说"we break up"。求竭泽抵达滑稽家时身上最多还剩多少件礼物，如果无法抵达滑稽家，或者已经没有礼物了则输出we break up
输入描述:
第一行输入五个整数 n, m, n1, n2, k，，
，
第二行输出 n1 个整数为可以选择为起点的车站的编号
第三行输出 n2 个整数为可以选择为终点的车站的编号
接下来 m 行每行三个整数表示存在一条从车站
到车站
的公交线路，花费为
，
，
输出描述:
输出一行，一个正整数为剩余的最多的礼物数量 或字符串we break up