import scala.annotation.tailrec

object Main extends App {
  override def main(args: Array[String]): Unit = {
    import scala.io.{StdIn => in}

    Iterator.continually(in.readLine()).takeWhile(_ != "0 0 0")
      .map(str => (str.split(" ")(0).toInt, str.split(" ")(1).toInt, str.split(" ")(2).toInt))
      .map(MNCap => {
        val fromTo = in.readLine()
        val map = for (i <- 1 to MNCap._1) yield in.readLine()
        val stations = for (i <- 1 to MNCap._2) yield in.readLine()
        new Solver(MNCap, fromTo, map, stations)
      }).map(_.solve()).foreach(println)

  }
}

class Solver(MNCap: (Int, Int, Int), fromTo: String, map: Seq[String], stationsSeq: Seq[String]) {
  val (m, n, cap) = MNCap
  val from = fromTo.split(" ")(0)
  val to = fromTo.split(" ")(1)
  val graph1 = map.map(fromToDistance => fromToDistance.split(" ")(0) -> (fromToDistance.split(" ")(1), fromToDistance.split(" ")(2).toInt)).groupBy(_._1)
  val graph2 = map.map(fromToDistance => fromToDistance.split(" ")(1) -> (fromToDistance.split(" ")(0), fromToDistance.split(" ")(2).toInt)).groupBy(_._1)
  val stations = stationsSeq.toSet

  case class FoldResult(visited: Map[String, Int], answer: Map[(String, Int), Int])

  def solve(): Int = {
    import scala.collection.mutable.{PriorityQueue => MPriorityQueue}

    val priorityQueue = MPriorityQueue[(Int, (String, Int))]()(Ordering.by(intString => -intString._1))

    priorityQueue += (0 -> (from, cap*10))
    val Sentinels = 2000 * 3000 + 1000

    def fold(folder: FoldResult, dequeued: (Int, (String, Int))): FoldResult = {
      val currentCityName = dequeued._2._1
      val reamingGas = if(stations contains currentCityName) cap*10 else dequeued._2._2
      val cityAndGasState = dequeued._2
      val distanceToCurrentCity = dequeued._1

      if(folder.visited.contains(to) ){
        priorityQueue.clear()
        folder
      } else if (currentCityName == to) {
        val newAnswer = folder.answer + (cityAndGasState -> distanceToCurrentCity)
        val newVisited = folder.visited + cityAndGasState
        FoldResult(newVisited, newAnswer)
      }
      else if (folder.visited.getOrElse(currentCityName,-1) > reamingGas) folder
      else {

        graph1
          .get(currentCityName).getOrElse(Seq()).map(fromAndTo => fromAndTo._2)
          .filter(cityAndGasState => cityAndGasState._2 <= reamingGas)
          .foreach(
            nextCityNameAndDistance => {
              val nextGasReaming = if (stations.contains(nextCityNameAndDistance._1)) cap * 10 else reamingGas - nextCityNameAndDistance._2
              if(folder.visited.getOrElse(nextCityNameAndDistance._1,-1) < nextGasReaming){
                priorityQueue += (distanceToCurrentCity + nextCityNameAndDistance._2 -> (nextCityNameAndDistance._1, nextGasReaming))
              }
            }
          )
        graph2.get(currentCityName).getOrElse(Seq()).map(fromAndTo => fromAndTo._2)
          .filter(cityAndGasState => cityAndGasState._2 <= reamingGas)
          .foreach(
            nextCityNameAndDistance => {
              val nextGasReaming = if (stations.contains(nextCityNameAndDistance._1)) cap * 10 else reamingGas - nextCityNameAndDistance._2
              if(folder.visited.getOrElse(nextCityNameAndDistance._1,-1) < nextGasReaming){
                priorityQueue += (distanceToCurrentCity + nextCityNameAndDistance._2 -> (nextCityNameAndDistance._1, nextGasReaming))
              }
            }
          )

        val newAnswer = folder.answer + (cityAndGasState -> distanceToCurrentCity)
        val newVisited = folder.visited + cityAndGasState
        FoldResult(newVisited, newAnswer)
      }
    }

    @tailrec
    def req(foldResult: FoldResult): FoldResult = {
//      println(priorityQueue +" "+ foldResult)
      if (priorityQueue.length == 0) foldResult else req(fold(foldResult, priorityQueue.dequeue()))
    }
    val result: FoldResult = req(FoldResult(Map[String, Int](), Map[(String, Int), Int]()))
//    println(result)
    result.answer.map(ans => ans._1._1 -> ans._2 ).getOrElse(to,-1)
  }
}

Measured memory_bytes: 734528