#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */
// verified : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A
// 負辺があると動作しない?
// O(E log V)
template<typename T>
vector<T> dijkstra(vector<vector<pair<int, T>>> &g, int s){
     
  int n = g.size();
  // numeric_limits がうまく使えない場合は自分で INF を定義する.
  const auto inf = INF;
  vector<T> dist(n, inf);

  using P = pair<T, int>;
  // 小さい順に取り出せる
  priority_queue<P, vector<P>, greater<P>> que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while(!que.empty()){
    T cost;
    int node;
    tie(cost, node) = que.top();
    que.pop();
    if(dist[node] < cost) continue;
    for(auto &e : g[node]){
      auto next_cost = cost + e.second;
      int next_node = e.first;
      if(dist[next_node] <= next_cost) continue;
      dist[next_node] = next_cost;
      que.emplace(next_cost, next_node);
    }
  }

  return dist;
}

int main() {
  
  int n, m, k, p; cin >> n >> m >> k >> p;
  p--;
  vector<vector<pair<int, lint>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    lint w; cin >> x >> y >> w;
    x--;
    y--;
    g[x].push_back({y, w});
    g[y].push_back({x, w});
  }

  vector<int> s(k);
  vector<int> t(k);
  for (int i = 0; i < k; i++) {
    cin >> s[i] >> t[i];
    s[i]--;
    t[i]--;
  }
  
  vector<vector<lint>> graph(2 * k + 1, vector<lint>(2 * k + 1, INF));
  for (int i = 0; i < 2 * k + 1; i++) {
    graph[i][i] = 0;
  }
  for (int i = 0; i < k; i++) {
    auto dist = dijkstra(g, s[i]);
    int u = i + 1;
    for (int j = 0; j < k; j++) {
      int v = j + 1;
      lint cost = dist[s[j]];
      graph[u][v] = graph[v][u] = cost;
    }

    for (int j = 0; j < k; j++) {
      int v = j + 1 + k;
      lint cost = dist[t[j]];
      graph[u][v] = graph[v][u] = cost;
    }

    {
      int v = 0;
      lint cost = dist[p];
      graph[u][v] = graph[v][u] = cost;
    }
  }
  
  for (int i = 0; i < k; i++) {
    auto dist = dijkstra(g, t[i]);
    int u = i + 1 + k;
    for (int j = 0; j < k; j++) {
      int v = j + 1;
      lint cost = dist[s[j]];
      graph[u][v] = graph[v][u] = cost;
    }

    for (int j = 0; j < k; j++) {
      int v = j + 1 + k;
      lint cost = dist[t[j]];
      graph[u][v] = graph[v][u] = cost;
    }

    {
      int v = 0;
      lint cost = dist[p];
      graph[u][v] = graph[v][u] = cost;
    }
  }

  int q = 2 * k + 1;
  for (int l = 0; l < q; l++) {
    for (int i = 0; i < q; i++) {
      for (int j = 0; j < q; j++) {
        graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
      }
    }
  }

  vector<vector<lint>> dp((1 << q), vector<lint>(q, INF));
  dp[1][0] = 0;
  for (int bit = 0; bit < (1 << q); bit++) {
    for (int u = 0; u < q; u++) {
      if (dp[bit][u] == INF) {
        continue;
      }

      for (int v = 0; v < q; v++) {
        // 訪問済みはとバス
        if (bit & (1 << v)) continue;
        // 荷物を持ってないなら，いけないよ
        if (v > k and !(bit & (1 << (v - k)))) continue;
        int nbit = bit | (1 << v);
        lint cost = graph[u][v];
        chmin(dp[nbit][v], dp[bit][u] + cost);
      }
    }
  }

  lint ans = INF;
  for (int u = 0; u < q; u++) {
    chmin(ans, dp[(1 << q) - 1][u]);
  }

  if (ans == INF) {
    cout << "Cannot deliver" << endl;
  } else {
    cout << ans << endl;
  }

  return 0;
}



Measured memory_bytes: 4180