硝烟在沧桑而深沉的大地上升起。
小 O 在战火的中心。
窗外满是废墟残骸，随时可以听见炮弹的轰鸣。
大使馆的电话传来，P 国战舰已经到达，请即刻出发。
【题目描述】
战时的交通线可以用一张 n 个点， m 条边的无向图表示，通过每条边仅需 1 个单位时间。由于战火的侵扰，每条边都有特定的危险系数 wi 。小 O 处在地图的 1 号点，撤侨中心设置在 n 号点。
为了尽可能降低被袭击的风险，小 O 希望选择一条最大的危险系数尽量小的路线。然而，为了降低风险而绕道太远也是万万不可的。
如果全图中 1 到 n 的最短时间为 T 个单位，那么选择的这条路线不能耗费超过 T+L 个单位的时间。
为了避免被当地的极端组织发现，大使馆提出了 k 条限制，要求小 O 不能连续经过 xi，yi，zi三个点。
请为小 O 找一条满足限制条件的，最大危险系数最小的路线，并输出这条路线上最大的危险系数。
【输入格式】
从 return.in 读入数据。
输入数据的第一行包含四个正整数n,m,k,L，意义与题目描述中相同。
接下来 m 行，每行三个正整数 u,v,w，代表有一条 u 点和 v 点间的双向道路，其危险系数为 w。
接下来 k 行，每行三个正整数 x,y,z，表示大使馆的路线限制。
【输出格式】
输出一行一个正整数，即最大危险系数的最小值。
【样例输入输出】
【样例输入】
9 8 2 30
1 5 1
1 4 4
4 5 4
5 6 16
6 8 4
4 7 5
7 6 5
8 9 4
1 4 5 1 5 6
【样例输出】
5
【子任务】
对于 100%的数据 k<=10
5，wi<=5000000。数据保证有解。
每个测试点的数据规模及特点如下表：
测试点编号 n 的范围 m 的范围 特殊限制
1 ≤4 ≤7 k=0,L=0
2，3 ≤4 ≤7
4 ≤100 ≤1000 k=0
5,6 ≤100 ≤1000 k≤1000
7 ≤500 ≤10000 k=0
8,9,10 ≤500 ≤10000