#include <bits/stdc++.h>
using namespace std;
#define INF 1<<29
typedef pair<int,int> P;

int a[1<<15][1001];
int main() {
  int n,m,k,p;
  cin >> n >> m >> k >> p;
  p--;
  vector<P> v[n];
  for(int i=0; i<m; i++) {
    int x,y,z;
    cin >> x >> y >> z;
    x--;y--;
    v[x].push_back(P(y,z));
    v[y].push_back(P(x,z));
  }
  int d[n][n];
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) d[i][j]=INF;
  }
  for(int i=0; i<n; i++) {
    priority_queue<P,vector<P>,greater<P> > que;
    que.push(P(0,i));
    d[i][i]=0;
    while(!que.empty()) {
      P p=que.top();que.pop();
      int c=p.first,x=p.second;
      if(c>d[i][x]) continue;
      for(int j=0; j<v[x].size(); j++) {
	int y=v[x][j].first;
	if(d[i][y]>c+v[x][j].second) {
	  d[i][y]=c+v[x][j].second;
	  que.push(P(d[i][y],y));
	}
      }
    }
  }
  P b[m];
  for(int i=0; i<k; i++) {
    cin >> b[i].first >> b[i].second;
    b[i].first--;b[i].second--;
  }
  for(int t=0; t<(1<<(k*2)); t++) {
    for(int i=0; i<n; i++) a[t][i]=INF;
  }
  a[0][p]=0;
  for(int t=0; t<(1<<(k*2)); t++) {
    for(int i=0; i<n; i++) {
      if(a[t][i]==INF) continue;
      for(int j=0; j<k; j++) {
	if(!(t&(1<<j))) a[t|(1<<j)][b[j].first]=min(a[t|(1<<j)][b[j].first],a[t][i]+d[i][b[j].first]);
	if(t&(1<<j) && !(t&(1<<(j+k)))) a[t|(1<<(j+k))][b[j].second]=min(a[t|(1<<(j+k))][b[j].second],a[t][i]+d[i][b[j].second]);
      }
    }
  }
  int ans=INF;
  for(int i=0; i<n; i++) ans=min(ans,a[(1<<(k*2))-1][i]);
  if(ans==INF) cout << "Cannot deliver" << endl;
  else cout << ans << endl;
  return 0;
}
