006 - 郵便局員を救え

物語

あなたは，この春に長年の夢だった郵便局に就職できました．担当する配達地域も決定し，ウキウキ気分で迎えた初仕事ですが，あまりに浮かれていたため郵便物を入れた袋に穴が空いているのに気づかず，入っていた郵便物を全部落としてしまいました．しかし，用意周到なあなたはすべての郵便物にGPSをつけていたため，どこに郵便物が落ちているかを知ることができます．
郵便物を拾いなおしていると予定していた配達時間を超えてしまうかもしれないので，あなたはできる限り短い時間で配達を終えたいと思っています．落としてしまったすべての郵便物を拾いなおして，それぞれの配達先に届ける最短の時間を求めなさい．

問題

あなたの担当する配達地域として無向グラフを考える．n頂点からなる無向グラフを考えたとき，それぞれの頂点には1からnの番号が付けられている．落とした郵便物の数と落ちている頂点，それぞれの郵便物の配達先の頂点が与えられたとき，すべての郵便物を回収して配達先に届ける最短時間を求めよ．このとき，ある郵便物をその郵便物の配達先に届ける場合に拾っていない他の郵便物が存在しても良い．また，配達終了時にはどの頂点にいても良いこととする．

ここで，1つの頂点には高々1つの郵便物か高々1つの配達先しかなく，出発する頂点には郵便物も配達先も存在しない．与えられる無向グラフは単純なグラフ，すなわち自己閉路や多重辺のないグラフである．

入力

n m k p
x1 y1 w1
...
xm ym wm
s1 t1
...
sk tk

最初の1行には無向グラフの頂点数 n (3≤n≤1,000)，辺数 m (1≤m≤2,000)，落とした郵便物の数 k (1≤k≤6)，始点 p (1≤p≤n) が与えられる．行中の入力項目は空白1個区切りで与えられる．
続く m 行ではグラフ中の辺の情報が与えられる．i 行目には i番目の辺の両端の頂点 x_i (1≤x_i≤n)，y_i (1≤y_i≤n) とその辺の重み w_i (1≤w_i≤1,000) が与えられる．
続く k 行の j 行目には落とした郵便物のある頂点 s_j (1≤s_j≤n) とその郵便物の配達先の頂点 t_j (1≤t_j≤n) が与えられる．
ここで，与えられるグラフは自己閉路や多重辺がなく，始点，各々の郵便物が落ちている頂点，各々の配達先はすべてが互いに異なる．

出力

頂点 p から出発して，すべての郵便物をそれぞれの配達先に届ける最短の時間を1行に表示せよ．
ただし，届けられない場合は "Cannot deliver" を出力せよ．

入出力例

入力例1

5 6 1 1
1 3 5
1 2 2
2 3 1
3 5 4
3 4 2
4 5 3
3 5

出力例1

7

入力例2

5 6 1 1
1 3 5
1 2 2
2 3 1
3 5 4
3 4 2
4 5 3
5 3

出力例2

11

入力例3

3 1 1 1
1 2 1
2 3

出力例3

Cannot deliver

入力例4

5 8 2 3
1 2 1
2 3 4
3 4 5
4 5 3
5 1 4
1 3 3
2 5 1
5 3 4
1 2
5 4

出力例4

8