#include <bits/stdc++.h>
const int INF = 0x1f1f1f1f;
int n, m, c, k, s[210], sz, first[610], next[300000], tail[300000], len[300000],
    h, heap[610], idx[610], dist[610][610], ss, vis[1000], from[1000];
void addedge(int u, int v, int l);
int hungary();
int match(int u);
void dijkstra();
void push(int k);
int pop();
void up(int u);
void down(int u);
void swap(int u, int v);
int main() {
  scanf("%d%d%d%d", &n, &m, &c, &k);
  int i, j;
  for (i = 1; i <= c; i++) scanf("%d", &s[i]);
  memset(first, 0, sizeof(first));
  int u, v, l;
  for (sz = 0, i = 1; i <= m; i++) {
    scanf("%d%d%d", &u, &v, &l);
    addedge(u, v, l);
    addedge(v, u, l);
  }
  for (i = 1; i <= c; i++) {
    ss = s[i];
    dijkstra();
  }
  int mint = 0, maxt = INF, mid;
  while (mint < maxt) {
    mid = (mint + maxt) / 2;
    memset(first, 0, sizeof(first));
    for (sz = 0, i = 1; i <= c; i++)
      for (j = 1; j <= n; j++)
        if (dist[s[i]][j] <= mid) addedge(i, j, 0);
    if (hungary() >= k)
      maxt = mid;
    else
      mint = mid + 1;
  }
  if (mint < INF)
    printf("%d\n", mint);
  else
    printf("-1\n");
  return 0;
}
void addedge(int u, int v, int l) {
  sz++;
  tail[sz] = v;
  len[sz] = l;
  next[sz] = first[u];
  first[u] = sz;
}
int hungary() {
  int ret = 0, i;
  memset(from, 0, sizeof(from));
  for (i = 1; i <= c; i++) {
    memset(vis, 0, sizeof(vis));
    if (match(i)) ret++;
  }
  return ret;
}
int match(int u) {
  int v, e;
  for (e = first[u]; e; e = next[e]) {
    v = tail[e];
    if (vis[v]) continue;
    vis[v] = 1;
    if (!from[v] || match(from[v])) {
      from[v] = u;
      return 1;
    }
  }
  return 0;
}
void dijkstra() {
  memset(dist[ss], 0x1f, sizeof(dist[ss]));
  dist[ss][ss] = 0;
  int i, u, v, e;
  for (h = 0, i = 1; i <= n; i++) push(i);
  while (h) {
    u = pop();
    for (e = first[u]; e; e = next[e]) {
      v = tail[e];
      if (dist[ss][u] + len[e] < dist[ss][v]) {
        dist[ss][v] = dist[ss][u] + len[e];
        up(idx[v]);
      }
    }
  }
}
void push(int k) {
  h++;
  heap[h] = k;
  idx[k] = h;
  up(h);
}
int pop() {
  int res = heap[1];
  heap[1] = heap[h--];
  down(1);
  return res;
}
void up(int u) {
  if (u > 1 && dist[ss][heap[u]] < dist[ss][heap[u / 2]]) {
    swap(u, u / 2);
    up(u / 2);
  }
}
void down(int u) {
  if (u * 2 > h) return;
  int v = u * 2;
  if (v + 1 <= h && dist[ss][heap[v + 1]] < dist[ss][heap[v]]) v++;
  if (dist[ss][heap[v]] < dist[ss][heap[u]]) {
    swap(u, v);
    down(v);
  }
}
void swap(int u, int v) {
  int t1, t2;
  t1 = heap[u];
  t2 = heap[v];
  heap[u] = t2;
  heap[v] = t1;
  idx[t1] = v;
  idx[t2] = u;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
const int INF = 0x1f1f1f1f;
int n, m, c, k, s[210], sz, first[610], next[300000], tail[300000], len[300000],
    h, heap[610], idx[610], dist[610][610], ss, vis[1000], from[1000];
void addedge(int u, int v, int l);
int hungary();
int match(int u);
void dijkstra();
void push(int k);
int pop();
void up(int u);
void down(int u);
void swap(int u, int v);
int main() {
  scanf("%d%d%d%d", &n, &m, &c, &k);
  int i, j;
  for (i = 1; i <= c; i++) scanf("%d", &s[i]);
  memset(first, 0, sizeof(first));
  int u, v, l;
  for (sz = 0, i = 1; i <= m; i++) {
    scanf("%d%d%d", &u, &v, &l);
    addedge(u, v, l);
    addedge(v, u, l);
  }
  for (i = 1; i <= c; i++) {
    ss = s[i];
    dijkstra();
  }
  int mint = 0, maxt = INF, mid;
  while (mint < maxt) {
    mid = (mint + maxt) / 2;
    memset(first, 0, sizeof(first));
    for (sz = 0, i = 1; i <= c; i++)
      for (j = 1; j <= n; j++)
        if (dist[s[i]][j] <= mid) addedge(i, j, 0);
    if (hungary() >= k)
      maxt = mid;
    else
      mint = mid + 1;
  }
  if (mint < INF)
    printf("%d\n", mint);
  else
    printf("-1\n");
  return 0;
}
void addedge(int u, int v, int l) {
  sz++;
  tail[sz] = v;
  len[sz] = l;
  next[sz] = first[u];
  first[u] = sz;
}
int hungary() {
  int ret = 0, i;
  memset(from, 0, sizeof(from));
  for (i = 1; i <= c; i++) {
    memset(vis, 0, sizeof(vis));
    if (match(i)) ret++;
  }
  return ret;
}
int match(int u) {
  int v, e;
  for (e = first[u]; e; e = next[e]) {
    v = tail[e];
    if (vis[v]) continue;
    vis[v] = 1;
    if (!from[v] || match(from[v])) {
      from[v] = u;
      return 1;
    }
  }
  return 0;
}
void dijkstra() {
  memset(dist[ss], 0x1f, sizeof(dist[ss]));
  dist[ss][ss] = 0;
  int i, u, v, e;
  for (h = 0, i = 1; i <= n; i++) push(i);
  while (h) {
    u = pop();
    for (e = first[u]; e; e = next[e]) {
      v = tail[e];
      if (dist[ss][u] + len[e] < dist[ss][v]) {
        dist[ss][v] = dist[ss][u] + len[e];
        up(idx[v]);
      }
    }
  }
}
void push(int k) {
  h++;
  heap[h] = k;
  idx[k] = h;
  up(h);
}
int pop() {
  int res = heap[1];
  heap[1] = heap[h--];
  down(1);
  return res;
}
void up(int u) {
  if (u > 1 && dist[ss][heap[u]] < dist[ss][heap[u / 2]]) {
    swap(u, u / 2);
    up(u / 2);
  }
}
void down(int u) {
  if (u * 2 > h) return;
  int v = u * 2;
  if (v + 1 <= h && dist[ss][heap[v + 1]] < dist[ss][heap[v]]) v++;
  if (dist[ss][heap[v]] < dist[ss][heap[u]]) {
    swap(u, v);
    down(v);
  }
}
void swap(int u, int v) {
  int t1, t2;
  t1 = heap[u];
  t2 = heap[v];
  heap[u] = t2;
  heap[v] = t1;
  idx[t1] = v;
  idx[t2] = u;
}

```