import scala.collection.mutable

object Main extends App {
  import scala.io.StdIn._

  val Array(n, m, k, p) = readLine.trim.split(' ').map(_.toInt)
  val edges = Array.tabulate(n){_ ⇒ Nil: List[(Int, Int)]}
  for (_ ← 0 until m){
    val Array(x, y, w) = readLine.trim.split(' ').map(_.toInt)
    edges(x - 1) ::= (y - 1, w)
    edges(y - 1) ::= (x - 1, w)
  }
  val post = Array.tabulate(n){_ ⇒ None: Option[Either[Int, Int]]}
  for (i ← 0 until k){
    val Array(s, t) = readLine.trim.split(' ').map(_.toInt)
    post(s - 1) = Some(Left(i))
    post(t - 1) = Some(Right(i))
  }
  val queue = mutable.PriorityQueue()(Ordering.by[(Int, Int, PostBag), Int](_._2).reverse)
  val minCost = Array.tabulate(n){_ ⇒ Array.tabulate(PostBag.exp(k)){_ ⇒ Int.MaxValue}}
  minCost(p - 1)(0) = 0
  queue.enqueue((p - 1, 0, PostBag(k)))
  while (queue.nonEmpty && !queue.head._3.isReleasedAll) {
    val (current, cost, bag) = queue.dequeue()
    if (minCost(current)(bag.toIndex) == cost){
      for ((next, c) ← edges(current)) {
        post(next) match {
          case Some(Right(i)) if bag.isCatch(i) ⇒
            if (minCost(next)(bag.releasePost(i).toIndex) > cost + c) {
              minCost(next)(bag.releasePost(i).toIndex) = cost + c
              queue.enqueue((next, cost + c, bag.releasePost(i)))
            }
          case Some(Left(i)) if !bag.isCatch(i) ⇒
            if (minCost(next)(bag.catchPost(i).toIndex) > cost + c){
              minCost(next)(bag.catchPost(i).toIndex) = cost + c
              queue.enqueue((next, cost + c, bag.catchPost(i)))
            }
          case _ ⇒
            if (minCost(next)(bag.toIndex) > cost + c){
              minCost(next)(bag.toIndex) = cost + c
              queue.enqueue((next, cost + c, bag))
            }
        }
      }
    }
  }
  if (queue.isEmpty) println("Cannot deliver")
  else println(queue.head._2)
  object PostBag {
    def apply(whole: Int): PostBag = PostBag(0, whole)
    def exp(e: Int): Int = {
      e match {
        case 0 ⇒ 1
        case 1 ⇒ 3
        case _ ⇒ exp(e / 2).let{i ⇒ i * i * exp(e % 2)}
      }
    }
  }
  case class PostBag(private val flags: Int, private val whole: Int) {
    def catchPost(post: Int): PostBag = {
      PostBag((flags / PostBag.exp(post + 1) * 3 + 1) * PostBag.exp(post) + (flags % PostBag.exp(post)), whole)
    }
    def releasePost(post: Int): PostBag = {
      PostBag((flags / PostBag.exp(post + 1) * 3 + 2) * PostBag.exp(post) + (flags % PostBag.exp(post)), whole)
    }
    def toIndex: Int = flags
    def isCatch(post: Int): Boolean = {
      (flags / PostBag.exp(post)) % 3 != 0
    }
    def isReleasedAll: Boolean = PostBag.exp(whole) - 1 == flags
  }
  implicit class Extension[T](val value :T) extends AnyVal {
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
    @inline
    def also(@inline func: T ⇒ Unit): T = {func(value); value}
    @inline
    def takeIf(@inline predicate: T ⇒ Boolean): Option[T] = Some(value).filter(predicate)
  }
}
