/*
 * 2672.cc: Rescue a Postal Worker
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 1000;
const int MAX_K = 6;
const int KBITS = 1 << MAX_K;

typedef long long ll;

const int INF = 1 << 30;
const ll LINF = 1LL << 60;

/* typedef */

typedef pair<int,int> pii;
typedef vector<pii> vpii;

struct Stat {
  int d, i, sbits, tbits;
  Stat() {}
  Stat(int _d, int _i, int _sbits, int _tbits):
    d(_d), i(_i), sbits(_sbits), tbits(_tbits) {}
  bool operator<(const Stat &s) const { return d > s.d; }
  void print() {
    printf("Stat: i=%d, sbits=%d, tbits=%d: d=%d\n", i, sbits, tbits, d);
  }
};

/* global variables */

vpii nbrs[MAX_N];
int ss[MAX_N], ts[MAX_N];
int dists[MAX_N][KBITS][KBITS];

/* subroutines */

/* main */

int main() {
  int n, m, k, p;
  cin >> n >> m >> k >> p;
  p--;

  for (int i = 0; i < m; i++) {
    int xi, yi, wi;
    cin >> xi >> yi >> wi;
    xi--, yi--;
    nbrs[xi].push_back(pii(yi, wi));
    nbrs[yi].push_back(pii(xi, wi));
  }

  for (int i = 0; i < k; i++) {
    int si, ti;
    cin >> si >> ti;
    si--, ti--;
    ss[si] = ts[ti] = (1 << i);
  }

  int kbits = 1 << k;
  
  for (int i = 0; i < n; i++)
    for (int sbits = 0; sbits < kbits; sbits++)
      for (int tbits = 0; tbits < kbits; tbits++)
	dists[i][sbits][tbits] = INF;
  dists[p][0][0] = 0;

  priority_queue<Stat> q;
  q.push(Stat(0, p, 0, 0));

  while (! q.empty()) {
    Stat u = q.top(); q.pop();
    if (dists[u.i][u.sbits][u.tbits] != u.d) continue;
    //u.print();
    
    if (u.tbits == kbits - 1) break;

    vpii &nbru = nbrs[u.i];
    for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int &vi = vit->first, vd = u.d + vit->second;
      int vsbits = u.sbits | ss[vi];
      int vtbits = (vsbits & ts[vi]) ? (u.tbits | ts[vi]) : u.tbits;

      if (dists[vi][vsbits][vtbits] > vd) {
	dists[vi][vsbits][vtbits] = vd;
	q.push(Stat(vd, vi, vsbits, vtbits));
      }
    }
  }

  int mind = INF;
  for (int i = 0; i < n; i++)
    if (mind > dists[i][kbits - 1][kbits - 1])
      mind = dists[i][kbits - 1][kbits - 1];

  if (mind >= INF) cout << "Cannot deliver" << endl;
  else printf("%d\n", mind);

  return 0;
}