You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

硝烟在沧桑而深沉的大地上升起。小O在战火的中心。

窗外满是废墟残骸，随时可以听见炮弹的轰鸣。

大使馆的电话传来，P国战舰已经到达，请即刻出发。

战时的交通线可以用一张$n$个点，$m$条边的无向图表示，通过每条边仅需$1$个单位时间。由于战火的侵扰，每条边都有特定的危险系数$w_i$。小O处在地图的$1$号点，撤侨中心设置在$n$号点。

为了尽可能降低被袭击的风险，小O希望选择一条最大的危险系数尽量小的路线。然而，为了降低风险而绕道太远也是 万万不可的。如果全图中$1$到$n$的最短时间为$T$个单位，那么选择的这条路线不能耗费超过$T+L$个单位的时间。为了避免被当地的极端组织发现，大使馆提出了$k$条限制，要求小O不能连续经过$x_i,y_i,z_i$ 三个点。

请为小O找一条满足限制且最大危险系数最小的路线，并输出这条路线上最大的危险系数。

输入格式

输入数据的第一行包含四个正整数$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\leq 10^5,w_i\leq 5\times 10^6$，其他满足下表所述限制：