#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define SZ(s) ((int)(s.size()))
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair<int,int> PI;


bool vis[1<<12][1000];
vector<PI> G[1000];
int si[1000];
int ti[1000];

int main(int argc, char *argv[])
{
  int n, m, k, p;
  cin >> n >> m >> k >> p;
  --p;
  rep(i, m){
    int x, y, c;
    cin >> x >> y >> c;
    --x, --y;
    G[x].pb(mp(y,c));
    G[y].pb(mp(x,c));
  }
  int go = 0;
  rep(i, k){
    int s, t;
    cin >> s >> t;
    --s, --t;
    si[s] = i + 1;
    ti[t] = i + 1;
    go = go * 4 + 2;
  }

  priority_queue<pair<int,PI> > q;
  q.push(mp(0,mp(p,0)));

  while(!q.empty()){
    int cc = -q.top().F;
    int cv = q.top().S.F;
    int st = q.top().S.S;
    q.pop();
    if(si[cv] && ((~st >> (si[cv] - 1)*2) & 2)){
      st |= 1 << (si[cv] - 1) * 2;
    }
    if(ti[cv] && ((st >> (ti[cv] - 1)*2) & 1)){
      st ^= 3 << (ti[cv]-1) * 2;
    }      
    if(vis[st][cv]) continue;
    vis[st][cv] = 1;
    if(st == go){
      cout << cc << endl;
      return 0;
    }
    
    for(auto e : G[cv]){
      int nst = st;
      q.push(mp(-cc-e.S,mp(e.F,nst)));
    }
  }

  cout << "Cannot deliver" << endl;
}