题目描述

HPL又要出水题了，但是这可太为难他了——菜鸡如他，又怎么可能想出神犇YZH出的那样的高质量神题，于是他开发了一种新型的出题方式。

他把考纲知识点全部列了出来，某些知识点间可以互相推导，这样一对知识点间可以连一条无向边，两个知识点间的一次推导是有思维难度的，用边权\(w\)来表示。一道题是由一个基础知识点\(A\)与一个考察知识点\(B\)组成的，这道题可行当且仅当基础知识点可以通过一些推导形成的推导思路推导出考察知识点，一种推导思路的难度为这个思路所用到的最难的推导的难度。这道题的难度\(x\)为这道题的所有推导思路的难度的最小值。

HPL想一次性出\(k\)道不同的题屯着，这样以后回去补文化课时也能留题了，为了照顾大家的感受，他想让出的题尽量简单，所以他想把自己出的所有题的难度控制在\(X\)以内。由于HPL热衷于膜杨~~.mp4~~ ，并且他发现，有一些特殊的推导是自带膜杨效果的，所以他希望他出的每一道题都能有一种难度在\(X\)以内的推导思路自带膜杨效果。

现在他想知道\(X\)最小是多少，因为他太菜了，所以他找到了你。

注意：
1. \(A \rightarrow B\)与\(B \rightarrow A\)是不同的两道题。
2. \(A,B\)不能是同一个知识点。
3. 推导思路不一定是一条简单路径。

输入格式

第一行有四个正整数 \(n,m,c,k\)，分别表示知识点的个数，推导的个数，特殊推导的个数，HPL想出的题数。
接下来 \(m\) 行，第 \(i + 1\) 行表示一个推导 \(i\) ，包含三个正整数\(A_i,B_i,w_i\)，表示这条推导连接的两个知识点以及这个推导的思维难度。
接下来 \(c\) 互不相同的正整数，每个数表示一个特殊推导的编号。

输出格式

只输出一行一个整数 \(X\)，HPL需要出的最难的题的最小难度。

样例输入

5 4 3 5
1 2 3
3 2 2
1 3 5
4 5 4
2 3 4

样例输出

3

样例解释

当难度为3时，HPL可以出\(1 \rightarrow 3,3 \rightarrow 1,2 \rightarrow 3,3 \rightarrow 2,4 \rightarrow 5,5 \rightarrow 4\)六道题。

约定与限制

对 \(30\%\) 的数据，\(n \leq 10,m \leq 100\) 。
对 \(50 \%\) 的数据，\(n \leq 10 ^ 3, m \leq 10 ^ 6\) 。
对 \(70\%\) 的数据，所有的推导都是膜杨推导。
对 \(100\%\) 的数据，\(n \leq 10 ^ 5,m \leq 10 ^ 6,w _ i \leq 10 ^ 9\)。
保证HPL能够出\(k\)道题，不存在重复的推导。

来自fstqwq幽怨的提示

lsw(HenryPigLi, HPL)说他读入优化习惯了。
我只能说…
输入输出数据可能很大，请考虑采用不那么低效的输入输出方式。
~~这题一点都不清真哼~~

来自HPL正直的提示

楼上神犇~~sb~~YZH的废话大家无视就好。
~~下次出题绝对不会再给读入优化模板了~~

template <class _T> inline void read(_T &_x) {
    int _t; bool flag = false;
    while ((_t = getchar()) != '-' && (_t < '0' || _t > '9')) ;
    if (_t == '-') _t = getchar(), flag = true; _x = _t - '0';
    while ((_t = getchar()) >= '0' && _t <= '9') _x = _x * 10 + _t - '0';
    if (flag) _x = -_x;
}