#include <bits/stdc++.h>
using namespace std;
const int INF = 2000000000;
struct Edge {
  int from, to, cap, flow, index;
  Edge(int from, int to, int cap, int flow, int index)
      : from(from), to(to), cap(cap), flow(flow), index(index) {}
};
struct Dinic {
  int N;
  vector<vector<Edge> > G;
  vector<Edge *> dad;
  vector<int> Q;
  Dinic(int N) : N(N), G(N), dad(N), Q(N) {}
  void AddEdge(int from, int to, int cap) {
    G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
    if (from == to) G[from].back().index++;
    G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
  }
  long long BlockingFlow(int s, int t) {
    fill(dad.begin(), dad.end(), (Edge *)NULL);
    dad[s] = &G[0][0] - 1;
    int head = 0, tail = 0;
    Q[tail++] = s;
    while (head < tail) {
      int x = Q[head++];
      for (int i = 0; i < G[x].size(); i++) {
        Edge &e = G[x][i];
        if (!dad[e.to] && e.cap - e.flow > 0) {
          dad[e.to] = &G[x][i];
          Q[tail++] = e.to;
        }
      }
    }
    if (!dad[t]) return 0;
    long long totflow = 0;
    for (int i = 0; i < G[t].size(); i++) {
      Edge *start = &G[G[t][i].to][G[t][i].index];
      int amt = INF;
      for (Edge *e = start; amt && e != dad[s]; e = dad[e->from]) {
        if (!e) {
          amt = 0;
          break;
        }
        amt = min(amt, e->cap - e->flow);
      }
      if (amt == 0) continue;
      for (Edge *e = start; amt && e != dad[s]; e = dad[e->from]) {
        e->flow += amt;
        G[e->to][e->index].flow -= amt;
      }
      totflow += amt;
    }
    return totflow;
  }
  long long GetMaxFlow(int s, int t) {
    long long totflow = 0;
    while (long long flow = BlockingFlow(s, t)) totflow += flow;
    return totflow;
  }
};
const int N = 605;
int dist[N][N];
vector<vector<pair<int, int> > > g(N);
void dij(int src) {
  for (int i = 0; i < N; i++) dist[src][i] = INF;
  dist[src][src] = 0;
  priority_queue<pair<int, int> > pq;
  pq.push(make_pair(0, src));
  while (pq.size()) {
    int node = pq.top().second;
    pq.pop();
    for (int i = 0; i < g[node].size(); i++) {
      int v = g[node][i].first;
      int w = g[node][i].second;
      if (dist[src][v] > dist[src][node] + w) {
        pq.push(make_pair(-dist[src][v], v));
        dist[src][v] = dist[src][node] + w;
      }
    }
  }
}
int n, m, teams, k;
int pos[N];
bool check(int ti) {
  Dinic din(n + teams + 10);
  int src = 0, sink = n + teams + 5;
  for (int i = 0; i < teams; i++) {
    din.AddEdge(src, i + 1, 1);
    for (int j = 1; j <= n; j++) {
      if (dist[pos[i]][j] <= ti) {
        din.AddEdge(i + 1, j + teams + 1, 1);
      }
    }
  }
  for (int i = 1; i <= n; i++) din.AddEdge(i + teams + 1, sink, 1);
  return din.GetMaxFlow(src, sink) >= k;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> teams >> k;
  for (int i = 0; i < teams; i++) cin >> pos[i];
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].push_back(make_pair(v, w));
    g[v].push_back(make_pair(u, w));
  }
  for (int i = 0; i < teams; i++) dij(pos[i]);
  int s = 0, e = 1731311, ans = -1;
  while (s <= e) {
    int mid = (s + e) >> 1;
    if (check(mid))
      e = mid - 1, ans = mid;
    else
      s = mid + 1;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Generate a CPP solution to 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 INF = 2000000000;
struct Edge {
  int from, to, cap, flow, index;
  Edge(int from, int to, int cap, int flow, int index)
      : from(from), to(to), cap(cap), flow(flow), index(index) {}
};
struct Dinic {
  int N;
  vector<vector<Edge> > G;
  vector<Edge *> dad;
  vector<int> Q;
  Dinic(int N) : N(N), G(N), dad(N), Q(N) {}
  void AddEdge(int from, int to, int cap) {
    G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
    if (from == to) G[from].back().index++;
    G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
  }
  long long BlockingFlow(int s, int t) {
    fill(dad.begin(), dad.end(), (Edge *)NULL);
    dad[s] = &G[0][0] - 1;
    int head = 0, tail = 0;
    Q[tail++] = s;
    while (head < tail) {
      int x = Q[head++];
      for (int i = 0; i < G[x].size(); i++) {
        Edge &e = G[x][i];
        if (!dad[e.to] && e.cap - e.flow > 0) {
          dad[e.to] = &G[x][i];
          Q[tail++] = e.to;
        }
      }
    }
    if (!dad[t]) return 0;
    long long totflow = 0;
    for (int i = 0; i < G[t].size(); i++) {
      Edge *start = &G[G[t][i].to][G[t][i].index];
      int amt = INF;
      for (Edge *e = start; amt && e != dad[s]; e = dad[e->from]) {
        if (!e) {
          amt = 0;
          break;
        }
        amt = min(amt, e->cap - e->flow);
      }
      if (amt == 0) continue;
      for (Edge *e = start; amt && e != dad[s]; e = dad[e->from]) {
        e->flow += amt;
        G[e->to][e->index].flow -= amt;
      }
      totflow += amt;
    }
    return totflow;
  }
  long long GetMaxFlow(int s, int t) {
    long long totflow = 0;
    while (long long flow = BlockingFlow(s, t)) totflow += flow;
    return totflow;
  }
};
const int N = 605;
int dist[N][N];
vector<vector<pair<int, int> > > g(N);
void dij(int src) {
  for (int i = 0; i < N; i++) dist[src][i] = INF;
  dist[src][src] = 0;
  priority_queue<pair<int, int> > pq;
  pq.push(make_pair(0, src));
  while (pq.size()) {
    int node = pq.top().second;
    pq.pop();
    for (int i = 0; i < g[node].size(); i++) {
      int v = g[node][i].first;
      int w = g[node][i].second;
      if (dist[src][v] > dist[src][node] + w) {
        pq.push(make_pair(-dist[src][v], v));
        dist[src][v] = dist[src][node] + w;
      }
    }
  }
}
int n, m, teams, k;
int pos[N];
bool check(int ti) {
  Dinic din(n + teams + 10);
  int src = 0, sink = n + teams + 5;
  for (int i = 0; i < teams; i++) {
    din.AddEdge(src, i + 1, 1);
    for (int j = 1; j <= n; j++) {
      if (dist[pos[i]][j] <= ti) {
        din.AddEdge(i + 1, j + teams + 1, 1);
      }
    }
  }
  for (int i = 1; i <= n; i++) din.AddEdge(i + teams + 1, sink, 1);
  return din.GetMaxFlow(src, sink) >= k;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> teams >> k;
  for (int i = 0; i < teams; i++) cin >> pos[i];
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].push_back(make_pair(v, w));
    g[v].push_back(make_pair(u, w));
  }
  for (int i = 0; i < teams; i++) dij(pos[i]);
  int s = 0, e = 1731311, ans = -1;
  while (s <= e) {
    int mid = (s + e) >> 1;
    if (check(mid))
      e = mid - 1, ans = mid;
    else
      s = mid + 1;
  }
  cout << ans << endl;
  return 0;
}

```