#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
struct edge{
    int to,cost;
    edge(int to,int cost):to(to),cost(cost){}
};
const int INF=1001001001;
int N,M,K,S;
vector<edge>G[1000];
int dist[1000];
void dijkstra(int s){
    fill_n(dist,N,INF);
    dist[s]=0;
    priority_queue<P,vector<P>,greater<P> >que;
    que.push(P(0,s));

    while(que.size()){
        P p=que.top();que.pop();
        if(dist[p.second]<p.first)continue;
        for(int i=0;i<G[p.second].size();i++){
            edge &e=G[p.second][i];
            if(dist[e.to]<=p.first+e.cost)continue;
            dist[e.to]=p.first+e.cost;
            que.push(P(dist[e.to],e.to));
        }
    }

}

int dp[1<<12][12];
int A[6],B[6];

int latte[12][12];
int main(){
    cin>>N>>M>>K>>S;S--;
    for(int i=0;i<M;i++){
        int a,b,c;
        cin>>a>>b>>c;a--;b--;
        G[a].push_back(edge(b,c));
        G[b].push_back(edge(a,c));
    }
    for(int i=0;i<K;i++){
        cin>>A[i]>>B[i];
        A[i]--;B[i]--;
    }

    fill_n(*dp,(1<<12)*12,INF);
    dijkstra(S);
    for(int i=0;i<K;i++){
        dp[1<<(i*2)][i*2]=dist[A[i]];
    }

    for(int i=0;i<K;i++){
        dijkstra(A[i]);
        for(int j=0;j<K;j++){
            latte[i*2][j*2]=dist[A[j]];
            latte[i*2][j*2+1]=dist[B[j]];
        }
        dijkstra(B[i]);
        for(int j=0;j<K;j++){
            latte[i*2+1][j*2]=dist[A[j]];
            latte[i*2+1][j*2+1]=dist[B[j]];
        }
    }


    for(int i=0;i<(1<<(2*K));i++){
        for(int j=0;j<2*K;j++){
            if(dp[i][j]==INF)continue;
            for(int k=0;k<2*K;k++){
                if(i>>k&1)continue;
                if(k%2==1&&(i>>(k-1)&1)==0)continue;
                dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+latte[j][k]);
            }
        }
    }

    int mi=INF;
    for(int i=0;i<2*K;i++)mi=min(mi,dp[(1<<(2*K))-1][i]);
    
    if(mi==INF)cout<<"Cannot deliver"<<endl;
    else cout<<mi<<endl;
    return 0;
}