CF852D.Exploration plan

The competitors of Bubble Cup X gathered after the competition and discussed what is the best way to get to know the host country and its cities.

After exploring the map of Serbia for a while, the competitors came up with the following facts: the country has V cities which are indexed with numbers from 1 to V, and there are E bi-directional roads that connect the cites. Each road has a weight (the time needed to cross that road). There are N teams at the Bubble Cup and the competitors came up with the following plan: each of the N teams will start their journey in one of the V cities, and some of the teams share the starting position.

They want to find the shortest time T, such that every team can move in these T minutes, and the number of different cities they end up in is at least K (because they will only get to know the cities they end up in). A team doesn't have to be on the move all the time, if they like it in a particular city, they can stay there and wait for the time to pass.

Please help the competitors to determine the shortest time T so it's possible for them to end up in at least K different cities or print -1 if that is impossible no matter how they move.

Note that there can exist multiple roads between some cities.

Bubble Cup X 的参赛者们在比赛结束后聚在一起，讨论了解主办国及其城市的最佳方式。

在研究了一段时间塞尔维亚地图后，参赛者们得出了以下事实：该国共有 $V$ 座城市，编号为 $1$ 至 $V$；另有 $E$ 条双向道路连接这些城市。每条道路具有一个权重（即穿越该道路所需的时间）。Bubble Cup 共有 $N$ 支队伍，参赛者们提出了如下计划：这 $N$ 支队伍将分别从 $V$ 座城市中的某一座出发，部分队伍可能从同一座城市出发。

他们希望找出最短时间 $T$，使得所有队伍均能在 $T$ 分钟内移动，并最终停留在至少 $K$ 个互不相同的城市中（因为他们仅能了解自己最终停留的城市）。一支队伍无需全程持续移动；若某支队伍喜欢某座特定城市，它可选择留在该城市并等待时间结束。

请帮助参赛者确定满足条件的最短时间 $T$；若无论怎样移动都不可能最终停留在至少 $K$ 个不同城市中，则输出 $-1$。

注意：某些城市之间可能存在多条道路。

The first line contains four integers: V, E, N and K (1 ≤  V  ≤  600,  1  ≤  E  ≤  20000,  1  ≤  N  ≤  min(V, 200),  1  ≤  K  ≤  N), number of cities, number of roads, number of teams and the smallest number of different cities they need to end up in, respectively.

The second line contains N integers, the cities where the teams start their journey.

Next E lines contain information about the roads in following format: A__i B__i T__i (1 ≤ A__i, B__i ≤ V,  1 ≤ T__i ≤ 10000), which means that there is a road connecting cities A__i and B__i, and you need T__i minutes to cross that road.

第一行包含四个整数：$V$、$E$、$N$ 和 $K$（$1 \leq V \leq 600$，$1 \leq E \leq 20000$，$1 \leq N \leq \min(V, 200)$，$1 \leq K \leq N$），分别表示城市的数量、道路的数量、队伍的数量，以及这些队伍最终必须分散到的最少不同城市数。

第二行包含 $N$ 个整数，表示各支队伍出发的城市编号。

接下来的 $E$ 行描述道路信息，每行格式为：$A_i\ B_i\ T_i$（$1 \leq A_i,\,B_i \leq V$，$1 \leq T_i \leq 10000$），表示城市 $A_i$ 与城市 $B_i$ 之间存在一条双向道路，穿越该道路需耗时 $T_i$ 分钟。

Output a single integer that represents the minimal time the teams can move for, such that they end up in at least K different cities or output -1 if there is no solution.

If the solution exists, result will be no greater than 1731311.

输出一个整数，表示队伍移动的最短时间，使得他们最终位于至少 K 个不同的城市；若无解，则输出 -1。

若解存在，则结果不会超过 1731311。

Three teams start from city 5, and two teams start from city 2. If they agree to move for 3 minutes, one possible situation would be the following: Two teams in city 2, one team in city 5, one team in city 3 , and one team in city 1. And we see that there are four different cities the teams end their journey at.

三支队伍从城市 5 出发，两支队伍从城市 2 出发。若他们约定移动 3 分钟，则一种可能的情形如下：两支队伍位于城市 2，一支队伍位于城市 5，一支队伍位于城市 3，一支队伍位于城市 1。我们发现，队伍最终到达的城市共有四个不同的城市。