import scala.collection.mutable

object Main extends App {

  import scala.io.StdIn._
  import scala.math._

  val Array(n, m, r, q) = readLine.trim.split(' ').map(_.toInt)
  val cards = Array.tabulate(n){_ ⇒ Nil: List[(Int, Int)]}
  for (_ ← 0 until m){
    val Array(a, b, c) = readLine.trim.split(' ').map(_.toInt)
    cards(b - 1)::=(a - 1, c)
  }
  val minChangeCost = Array.tabulate(r){_ ⇒ Array.tabulate(n){_ ⇒ Long.MaxValue}}
  for (i ← 0 until r){
    val memo = minChangeCost(i)
    val queue = mutable.PriorityQueue()(Ordering.by[(Int, Long), Long](_._2).reverse)
    for (j ← (i + r - 1) % r until n by r){
      memo(j) = 0L
      queue.enqueue((j, 0L))
    }
    while (queue.nonEmpty){
      val (top, distance) = queue.dequeue()
      if (memo(top) == distance){
        for ((to, cost) ← cards(top)){
          if (memo(to) - cost > distance){
            memo(to) = distance + cost
            queue.enqueue((to, distance + cost))
          }
        }
      }
    }
  }
  println(
    (for (_ ← 0 until q) yield {
      val Array(x, y, z) = readLine.trim.split(' ').map(_.toInt)
      minChangeCost.map{memo ⇒
        if (memo(x - 1) < z - memo(y - 1)) z - memo(x - 1) - memo(y - 1)
        else 0L
      }.max
    }).sum
  )


  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}
