#include <utility>
#include <limits>
#include <queue>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
namespace lc {
template <class WeightType>
struct EdgeWithWeight {
	int to;
	WeightType weight;
	EdgeWithWeight() : to(0), weight() { }
	EdgeWithWeight(int to, const WeightType &weight)
		: to(to), weight(weight)
	{ }
};
}
namespace lc {
template <typename EdgeType>
class AdjacencyList {
public:
	typedef std::vector<EdgeType> ListType;
private:
	std::vector<ListType> m_lists;
public:
	explicit AdjacencyList(int n = 0)
		: m_lists(n)
	{ }
	int size() const { return m_lists.size(); }
	template <typename... Args>
	void add_edge(int u, Args&&... args){
		m_lists[u].emplace_back(args...);
	}
	const ListType &operator[](int u) const { return m_lists[u]; }
};
}
namespace lc {
template <typename EdgeType>
auto sssp_dijkstra(int source, const AdjacencyList<EdgeType> &graph)
	-> std::vector<decltype(EdgeType().weight)>
{
	typedef decltype(EdgeType().weight) weight_type;
	typedef std::pair<weight_type, int> weighted_pair;
	const auto inf = std::numeric_limits<weight_type>::max();
	const int n = graph.size();
	std::vector<weight_type> result(n, inf);
	std::priority_queue<weighted_pair, std::vector<weighted_pair>, std::greater<weighted_pair>> pq;
	result[source] = weight_type();
	pq.push(std::make_pair(result[source], source));
	while(!pq.empty()){
		const auto d = pq.top().first;
		const auto u = pq.top().second;
		pq.pop();
		if(result[u] < d){ continue; }
		for(const auto &e : graph[u]){
			const auto v = e.to;
			const auto w = e.weight;
			if(d + w < result[v]){
				result[v] = d + w;
				pq.push(std::make_pair(result[v], v));
			}
		}
	}
	return result;
}
}
using namespace std;
typedef lc::EdgeWithWeight<int>	Edge;
static const int INF = 1000000000;
int main(){
	ios_base::sync_with_stdio(false);
	int n, m, k, p;
	cin >> n >> m >> k >> p;
	--p;
	lc::AdjacencyList<Edge> graph(n);
	for(int i = 0; i < m; ++i){
		int a, b, c;
		cin >> a >> b >> c;
		--a; --b;
		graph.add_edge(a, b, c);
		graph.add_edge(b, a, c);
	}
	vector<int> s(k), t(k), check(n, -1);
	check[p] = k * 2;
	for(int i = 0; i < k; ++i){
		cin >> s[i] >> t[i];
		--s[i]; --t[i];
		check[s[i]] = i * 2 + 0;
		check[t[i]] = i * 2 + 1;
	}
	vector<vector<int>> mat(k * 2 + 1, vector<int>(k * 2 + 1, INF));
	bool impossible = false;
	for(int i = 0; i < n; ++i){
		if(check[i] < 0){ continue; }
		const auto dists = lc::sssp_dijkstra(i, graph);
		for(int j = 0; j < n; ++j){
			if(check[j] < 0){ continue; }
			mat[check[i]][check[j]] = min(INF, dists[j]);
			if(dists[j] >= INF){ impossible = true; }
		}
	}
	if(impossible){
		cout << "Cannot deliver" << endl;
		return 0;
	}
	vector<vector<int>> dp(2 << (k * 2), vector<int>(k * 2 + 1, INF));
	dp[1 << (2 * k)][2 * k] = 0;
	for(int i = 0; i < (2 << (k * 2)); ++i){
		for(int j = 0; j <= 2 * k; ++j){
			if(dp[i][j] >= INF){ continue; }
			const int cur = dp[i][j];
			for(int t = 0; t <= 2 * k; ++t){
				if(i & (1 << t)){ continue; }
				if(t % 2 == 1 && !(i & (1 << (t - 1)))){ continue; }
				dp[i | (1 << t)][t] =
					min(dp[i | (1 << t)][t], cur + mat[j][t]);
			}
		}
	}
	int answer = INF;
	for(int i = 0; i <= 2 * k; ++i){
		answer = min(answer, dp[(2 << (k * 2)) - 1][i]);
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 1824