#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
struct Maxflow {
  static const int MAXV = 20010;
  static const int INF = 1000000;
  struct Edge {
    int v, c, r;
    Edge(int _v, int _c, int _r) : v(_v), c(_c), r(_r) {}
  };
  int s, t;
  vector<Edge> G[MAXV * 2];
  int iter[MAXV * 2], d[MAXV * 2], gap[MAXV * 2], tot;
  void init(int x) {
    tot = x + 2;
    s = x + 1, t = x + 2;
    for (int i = 0; i <= tot; i++) {
      G[i].clear();
      iter[i] = d[i] = gap[i] = 0;
    }
  }
  void addEdge(int u, int v, int c) {
    G[u].push_back(Edge(v, c, (int)(G[v]).size()));
    G[v].push_back(Edge(u, 0, (int)(G[u]).size() - 1));
  }
  int dfs(int p, int flow) {
    if (p == t) return flow;
    for (int &i = iter[p]; i < (int)(G[p]).size(); i++) {
      Edge &e = G[p][i];
      if (e.c > 0 && d[p] == d[e.v] + 1) {
        int f = dfs(e.v, min(flow, e.c));
        if (f) {
          e.c -= f;
          G[e.v][e.r].c += f;
          return f;
        }
      }
    }
    if ((--gap[d[p]]) == 0)
      d[s] = tot;
    else {
      d[p]++;
      iter[p] = 0;
      ++gap[d[p]];
    }
    return 0;
  }
  int solve() {
    int res = 0;
    gap[0] = tot;
    for (res = 0; d[s] < tot; res += dfs(s, INF))
      ;
    return res;
  }
} flow;
void build() {}
int v, e, n, K, s[666];
int d[666][666], ss[666];
void init() {
  v = getint();
  e = getint();
  n = getint();
  K = getint();
  for (int i = 1; i <= n; i++) ss[getint()]++;
  for (int i = 1; i <= v; i++) {
    for (int j = 1; j <= v; j++) d[i][j] = (1731311 * 2);
    d[i][i] = 0;
  }
  while (e--) {
    int ai = getint();
    int bi = getint();
    int wi = getint();
    if (wi < d[ai][bi]) d[ai][bi] = d[bi][ai] = wi;
  }
  for (int k = 1; k <= v; k++)
    for (int i = 1; i <= v; i++)
      for (int j = 1; j <= v; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
}
bool okay(int tar) {
  flow.init(v + v);
  for (int i = 1; i <= v; i++) {
    if (ss[i]) flow.addEdge(flow.s, i, ss[i]);
    flow.addEdge(v + i, flow.t, 1);
    for (int j = 1; j <= v; j++)
      if (d[i][j] <= tar) flow.addEdge(i, v + j, 1);
  }
  return flow.solve() >= K;
}
void solve() {
  int bl = 0, br = 1731311, ba = -1;
  while (bl <= br) {
    int bmid = (bl + br) >> 1;
    if (okay(bmid))
      ba = bmid, br = bmid - 1;
    else
      bl = bmid + 1;
  }
  printf("%d\n", ba);
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

### Prompt

In cpp, your task is to solve the following problem:

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.

Input

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: Ai Bi Ti (1 ≤ Ai, Bi ≤ V, 1 ≤ Ti ≤ 10000), which means that there is a road connecting cities Ai and Bi, and you need Ti minutes to cross that road.

Output

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.

Example

Input

6 7 5 4
5 5 2 2 5
1 3 3
1 5 2
1 6 5
2 5 4
2 6 7
3 4 11
3 5 3


Output

3

Note

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.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
struct Maxflow {
  static const int MAXV = 20010;
  static const int INF = 1000000;
  struct Edge {
    int v, c, r;
    Edge(int _v, int _c, int _r) : v(_v), c(_c), r(_r) {}
  };
  int s, t;
  vector<Edge> G[MAXV * 2];
  int iter[MAXV * 2], d[MAXV * 2], gap[MAXV * 2], tot;
  void init(int x) {
    tot = x + 2;
    s = x + 1, t = x + 2;
    for (int i = 0; i <= tot; i++) {
      G[i].clear();
      iter[i] = d[i] = gap[i] = 0;
    }
  }
  void addEdge(int u, int v, int c) {
    G[u].push_back(Edge(v, c, (int)(G[v]).size()));
    G[v].push_back(Edge(u, 0, (int)(G[u]).size() - 1));
  }
  int dfs(int p, int flow) {
    if (p == t) return flow;
    for (int &i = iter[p]; i < (int)(G[p]).size(); i++) {
      Edge &e = G[p][i];
      if (e.c > 0 && d[p] == d[e.v] + 1) {
        int f = dfs(e.v, min(flow, e.c));
        if (f) {
          e.c -= f;
          G[e.v][e.r].c += f;
          return f;
        }
      }
    }
    if ((--gap[d[p]]) == 0)
      d[s] = tot;
    else {
      d[p]++;
      iter[p] = 0;
      ++gap[d[p]];
    }
    return 0;
  }
  int solve() {
    int res = 0;
    gap[0] = tot;
    for (res = 0; d[s] < tot; res += dfs(s, INF))
      ;
    return res;
  }
} flow;
void build() {}
int v, e, n, K, s[666];
int d[666][666], ss[666];
void init() {
  v = getint();
  e = getint();
  n = getint();
  K = getint();
  for (int i = 1; i <= n; i++) ss[getint()]++;
  for (int i = 1; i <= v; i++) {
    for (int j = 1; j <= v; j++) d[i][j] = (1731311 * 2);
    d[i][i] = 0;
  }
  while (e--) {
    int ai = getint();
    int bi = getint();
    int wi = getint();
    if (wi < d[ai][bi]) d[ai][bi] = d[bi][ai] = wi;
  }
  for (int k = 1; k <= v; k++)
    for (int i = 1; i <= v; i++)
      for (int j = 1; j <= v; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
}
bool okay(int tar) {
  flow.init(v + v);
  for (int i = 1; i <= v; i++) {
    if (ss[i]) flow.addEdge(flow.s, i, ss[i]);
    flow.addEdge(v + i, flow.t, 1);
    for (int j = 1; j <= v; j++)
      if (d[i][j] <= tar) flow.addEdge(i, v + j, 1);
  }
  return flow.solve() >= K;
}
void solve() {
  int bl = 0, br = 1731311, ba = -1;
  while (bl <= br) {
    int bmid = (bl + br) >> 1;
    if (okay(bmid))
      ba = bmid, br = bmid - 1;
    else
      bl = bmid + 1;
  }
  printf("%d\n", ba);
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

```