{"raw_statement":[{"iden":"statement","content":"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.\n\nAfter 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.\n\nThey 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.\n\nPlease 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.\n\nNote that there can exist multiple roads between some cities."},{"iden":"input","content":"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.\n\nThe second line contains _N_ integers, the cities where the teams start their journey.\n\nNext _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."},{"iden":"output","content":"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.\n\nIf the solution exists, result will be no greater than 1731311."},{"iden":"example","content":"Input\n\n6 7 5 4\n5 5 2 2 5\n1 3 3\n1 5 2\n1 6 5\n2 5 4\n2 6 7\n3 4 11\n3 5 3\n\nOutput\n\n3"},{"iden":"note","content":"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."}],"translated_statement":[{"iden":"statement","content":"Bubble Cup X 的参赛者们在比赛结束后聚在一起，讨论了解东道国及其城市的最佳方式。\n\n在研究了塞尔维亚的地图一段时间后，参赛者们得出了以下结论：该国有 #cf_span[V] 个城市，编号从 #cf_span[1] 到 #cf_span[V]，并有 #cf_span[E] 条双向道路连接这些城市。每条道路都有一个权重（通过该道路所需的时间）。Bubble Cup 上共有 #cf_span[N] 支队伍，参赛者们提出了以下计划：每支 #cf_span[N] 支队伍将从 #cf_span[V] 个城市中的一个出发，部分队伍共享相同的起点。\n\n他们希望找到最短时间 #cf_span[T]，使得每支队伍都能在 #cf_span[T] 分钟内移动，并且最终到达的不同城市数量至少为 #cf_span[K]（因为他们只会了解最终到达的城市）。队伍不必一直移动，如果他们喜欢某个城市，可以留在那里等待时间流逝。\n\n请帮助参赛者们确定最短时间 #cf_span[T]，使得他们能够最终到达至少 #cf_span[K] 个不同的城市；如果无论如何移动都无法实现，请输出 _-1_。\n\n注意：某些城市之间可能存在多条道路。\n\n第一行包含四个整数：#cf_span[V], #cf_span[E], #cf_span[N] 和 #cf_span[K]（1 ≤  V  ≤  600，  1  ≤  E  ≤  20000，  1  ≤  N  ≤  min(V, 200)，  1  ≤  K  ≤  N），分别表示城市数量、道路数量、队伍数量和所需到达的最少不同城市数量。\n\n第二行包含 #cf_span[N] 个整数，表示每支队伍的起始城市。\n\n接下来的 #cf_span[E] 行，每行包含三条信息：#cf_span[Ai Bi Ti]（1 ≤ Ai, Bi ≤ V，  1 ≤ Ti ≤ 10000），表示存在一条连接城市 #cf_span[Ai] 和 #cf_span[Bi] 的道路，通过该道路需要 #cf_span[Ti] 分钟。\n\n请输出一个整数，表示队伍移动的最短时间，使得他们最终到达至少 #cf_span[K] 个不同的城市；如果无解，请输出 _-1_。\n\n如果存在解，结果不会超过 #cf_span[1731311]。\n\n三支队伍从城市 5 出发，两支队伍从城市 2 出发。如果他们同意移动 3 分钟，一种可能的情况是：两支队伍在城市 2，一支队伍在城市 5，一支队伍在城市 3，一支队伍在城市 1。此时，他们最终到达了四个不同的城市。"},{"iden":"input","content":"第一行包含四个整数：#cf_span[V], #cf_span[E], #cf_span[N] 和 #cf_span[K]（1 ≤  V  ≤  600，  1  ≤  E  ≤  20000，  1  ≤  N  ≤  min(V, 200)，  1  ≤  K  ≤  N），分别表示城市数量、道路数量、队伍数量和所需到达的最少不同城市数量。第二行包含 #cf_span[N] 个整数，表示每支队伍的起始城市。接下来的 #cf_span[E] 行，每行包含三条信息：#cf_span[Ai Bi Ti]（1 ≤ Ai, Bi ≤ V，  1 ≤ Ti ≤ 10000），表示存在一条连接城市 #cf_span[Ai] 和 #cf_span[Bi] 的道路，通过该道路需要 #cf_span[Ti] 分钟。"},{"iden":"output","content":"输出一个整数，表示队伍移动的最短时间，使得他们最终到达至少 #cf_span[K] 个不同的城市；如果无解，请输出 _-1_。如果存在解，结果不会超过 #cf_span[1731311]。"},{"iden":"note","content":"三支队伍从城市 5 出发，两支队伍从城市 2 出发。如果他们同意移动 3 分钟，一种可能的情况是：两支队伍在城市 2，一支队伍在城市 5，一支队伍在城市 3，一支队伍在城市 1。此时，他们最终到达了四个不同的城市。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ V, E, N, K \\in \\mathbb{Z}^+ $ denote the number of cities, roads, teams, and minimum required distinct destination cities, respectively.  \nLet $ S = (s_1, s_2, \\dots, s_N) \\in \\{1, \\dots, V\\}^N $ be the multiset of starting cities of the $ N $ teams.  \nLet $ G = (V, E, w) $ be an undirected weighted graph, where $ w: E \\to \\mathbb{Z}^+ $ assigns to each edge $ (u,v) $ a travel time $ t_{uv} $.  \n\n**Constraints**  \n1. $ 1 \\le V \\le 600 $, $ 1 \\le E \\le 20000 $, $ 1 \\le N \\le \\min(V, 200) $, $ 1 \\le K \\le N $  \n2. $ 1 \\le t_{uv} \\le 10000 $ for each road $ (u,v) \\in E $  \n3. Multiple edges between same pair of cities are allowed.  \n\n**Objective**  \nCompute the minimal time $ T \\in \\mathbb{R}_{\\ge 0} $ such that, for each team $ i \\in \\{1, \\dots, N\\} $, there exists a destination city $ d_i \\in \\{1, \\dots, V\\} $ with $ \\text{dist}(s_i, d_i) \\le T $, and the set $ \\{d_1, \\dots, d_N\\} $ contains at least $ K $ distinct cities.  \nIf no such $ T $ exists, output $ -1 $.  \n\n**Note**  \n$ \\text{dist}(u,v) $ denotes the shortest path distance between cities $ u $ and $ v $ in $ G $.","simple_statement":null,"has_page_source":false}