#include <cstring>
#include <map>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <queue>
#include <set>

using namespace std;

vector<pair<int, int> > g[1000];
vector<int> d[1000];

int s[8];
int t[8];

int n, m, k, p;
map<int, int> ids;
int poss[32];
const int inf = 1 << 30;

int memo[32][1 << 6][1 << 6];

int solve(int pos, int have, int done){
  if(done == (1 << k) - 1) return 0;
  if(memo[pos][have][done] != -1) return memo[pos][have][done];

  const int p = poss[pos];
  int ret = inf;

  REP(i,k) if((have & (1 << i)) == 0 && (done & (1 << i)) == 0){
    const int next = s[i];
    const int cost = d[p][next];
    if(cost == -1) continue;
    ret = min(ret, cost + solve(ids[next], have | (1 << i), done));
  }

  REP(i,k) if((have & (1 << i)) != 0 && (done & (1 << i)) == 0){
    const int next = t[i];
    const int cost = d[p][next];
    if(cost == -1) continue;
    ret = min(ret, cost + solve(ids[next], have ^ (1 << i), done | (1 << i)));
  }

  return memo[pos][have][done] = ret;
}

vector<int> dijkstra(int start){
  vector<int> ret(n, -1);
  typedef pair<int, int> data;
  priority_queue<data, vector<data>, greater<data> > pq;
  pq.push(make_pair(0, start));
  while(pq.size()){
    const data dt = pq.top(); pq.pop();
    const int cost = dt.first;
    const int pos = dt.second;

    if(ret[pos] != -1) continue;
    ret[pos] = cost;

    REP(i,g[pos].size()){
      const int next = g[pos][i].first;
      if(ret[next] == -1){
	pq.push(make_pair(cost + g[pos][i].second, next));
      }
    }
  }

  return ret;
}


int main(){
  n = getInt();
  m = getInt();
  k = getInt();
  p = getInt() - 1;

  REP(i,m){
    const int x = getInt() - 1;
    const int y = getInt() - 1;
    const int w = getInt();

    g[x].push_back(make_pair(y, w));
    g[y].push_back(make_pair(x, w));
  }

  REP(i,k){
    s[i] = getInt() - 1;
    t[i] = getInt() - 1;
  }

  int id = 0;
  REP(i,k){ poss[id] = s[i]; ids[s[i]] = id++; }
  REP(i,k){ poss[id] = t[i]; ids[t[i]] = id++; }

  d[p] = dijkstra(p);
  REP(i,k){
    d[s[i]] = dijkstra(s[i]);
    d[t[i]] = dijkstra(t[i]);
  }

  /*
  REP(i,n){
    printf("%d:", i);
    if(d[i].size() != 0)
      REP(j,n) printf(" %d", d[i][j]);
    puts("");
  }
  */

  memset(memo, -1, sizeof(memo));

  int ans = inf;
  REP(i,k) if(d[p][s[i]] != -1){
    ans = min(ans, d[p][s[i]] + solve(i, 1 << i, 0));
  }

  if(ans == inf){
    puts("Cannot deliver");
  }else{
    printf("%d\n", ans);
  }

  return 0;
}