#include <bits/stdc++.h>
using namespace std;
const int Imx = 2147483647;
const long long Lbig = 2e18;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c == ' ' || c == '\n') c = _buff.get();
  return c;
}
struct Matching {
  int n, m;
  int mx[611], my[611];
  bool f[611][611];
  int tag[611], cur;
  void init(int N, int M) {
    n = N;
    m = M;
    memset(mx, 0, sizeof(mx));
    memset(my, 0, sizeof(my));
    memset(f, 0, sizeof(f));
    memset(tag, 0, sizeof(tag));
    cur = 0;
  }
  void sete(int x, int y) { f[x][y] = 1; }
  bool dfs(int x) {
    if (tag[x] == cur) return false;
    tag[x] = cur;
    for (int y = 1; y <= m; y++) {
      if (f[x][y]) {
        if (!my[y] || dfs(my[y])) {
          mx[x] = y;
          my[y] = x;
          return true;
        }
      }
    }
    return false;
  }
  int solve() {
    int ans = 0;
    for (int i = 1; i <= n; i++) cur++, ans += dfs(i);
    return ans;
  }
} graph;
int n, m, tn, K;
int st[611];
int w[611][611];
bool check(int T) {
  graph.init(tn, n);
  for (int i = 1; i <= tn; i++) {
    for (int j = 1; j <= n; j++) {
      if (w[st[i]][j] <= T) {
        graph.sete(i, j);
      }
    }
  }
  return graph.solve() >= K;
}
int main() {
  n = getnum(), m = getnum();
  tn = getnum(), K = getnum();
  for (int i = 1; i <= tn; i++) st[i] = getnum();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) w[i][j] = i == j ? 0 : mod;
  for (int i = 1; i <= m; i++) {
    int x, y, t;
    x = getnum(), y = getnum(), t = getnum();
    w[x][y] = min(w[x][y], t);
    w[y][x] = min(w[y][x], t);
  }
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        w[i][j] = w[i][k] + w[k][j] < w[i][j] ? w[i][k] + w[k][j] : w[i][j];
  int l = 0, r = 1731311;
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid))
      r = mid - 1;
    else
      l = mid + 1;
  }
  if (l > 1731311)
    puts("-1");
  else
    cout << l << endl;
  return 0;
}

### Prompt

Create a solution in CPP for 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>
using namespace std;
const int Imx = 2147483647;
const long long Lbig = 2e18;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c == ' ' || c == '\n') c = _buff.get();
  return c;
}
struct Matching {
  int n, m;
  int mx[611], my[611];
  bool f[611][611];
  int tag[611], cur;
  void init(int N, int M) {
    n = N;
    m = M;
    memset(mx, 0, sizeof(mx));
    memset(my, 0, sizeof(my));
    memset(f, 0, sizeof(f));
    memset(tag, 0, sizeof(tag));
    cur = 0;
  }
  void sete(int x, int y) { f[x][y] = 1; }
  bool dfs(int x) {
    if (tag[x] == cur) return false;
    tag[x] = cur;
    for (int y = 1; y <= m; y++) {
      if (f[x][y]) {
        if (!my[y] || dfs(my[y])) {
          mx[x] = y;
          my[y] = x;
          return true;
        }
      }
    }
    return false;
  }
  int solve() {
    int ans = 0;
    for (int i = 1; i <= n; i++) cur++, ans += dfs(i);
    return ans;
  }
} graph;
int n, m, tn, K;
int st[611];
int w[611][611];
bool check(int T) {
  graph.init(tn, n);
  for (int i = 1; i <= tn; i++) {
    for (int j = 1; j <= n; j++) {
      if (w[st[i]][j] <= T) {
        graph.sete(i, j);
      }
    }
  }
  return graph.solve() >= K;
}
int main() {
  n = getnum(), m = getnum();
  tn = getnum(), K = getnum();
  for (int i = 1; i <= tn; i++) st[i] = getnum();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) w[i][j] = i == j ? 0 : mod;
  for (int i = 1; i <= m; i++) {
    int x, y, t;
    x = getnum(), y = getnum(), t = getnum();
    w[x][y] = min(w[x][y], t);
    w[y][x] = min(w[y][x], t);
  }
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        w[i][j] = w[i][k] + w[k][j] < w[i][j] ? w[i][k] + w[k][j] : w[i][j];
  int l = 0, r = 1731311;
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid))
      r = mid - 1;
    else
      l = mid + 1;
  }
  if (l > 1731311)
    puts("-1");
  else
    cout << l << endl;
  return 0;
}

```