package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
  "container/heap"
)

type Item struct {
  Priority int
  Entry interface{}
}
type Heap []*Item
func (H Heap) Len() int { return len(H) }
func (H Heap) Less(i, j int) bool { return H[i].Priority < H[j].Priority }
func (H Heap) Swap(i, j int) { H[i], H[j] = H[j], H[i] }
func (H *Heap) Pop() interface{} {
  Old := *H
  n := len(Old)
  item := Old[n - 1]
  *H = Old[0:n - 1]
  return item
}
func (H *Heap) Push(x interface{}) {
  item := x.(*Item)
  *H = append(*H, item)
}
type PriorityQueue struct {
  Comparator func(e interface{}) int
  Items Heap
}
func (PQ *PriorityQueue) Push(e interface{}) {
  item := Item{PQ.Comparator(e), e}
  heap.Push(&PQ.Items, &item)
}
func (PQ *PriorityQueue) Pop() interface{} {
  return heap.Pop(&PQ.Items).(*Item).Entry
}
func InitPQ(F func(interface{}) int) PriorityQueue {
  var H Heap
  return PriorityQueue{F, H}
}

func Solve() {
  var N, M, S int
  NextInt(&N, &M, &S)
  G := make([][][]int, N)
  for i := range G { G[i] = make([][]int, 0) }
  var U, V, A, B int
  m := 0
  for i := 0; i < M; i++ {
    NextInt(&U, &V, &A, &B)
    m = MaxInt(A, m)
    U--
    V--
    G[U] = append(G[U], []int{V, A, B})
    G[V] = append(G[V], []int{U, A, B})
  }
  L := m * (N - 1)
  R := make([][]int, N)
  for i := range R { NextIntVec(&R[i]) }
  DP := make([][]int, N)
  for i := range DP {
    DP[i] = make([]int, L + 1)
    for j := range DP[i] { DP[i][j] = -1 }
  }
  for j := 0; j <= MinInt(S, L); j++ { DP[0][j] = 0 }
  Q := make([]int, 0)
  Q = append(Q, 0)
  var u, v, a, b, k int
  var add bool
  for 0 < len(Q) {
    u = Q[0]
    Q = Q[1:]
    for j := range DP[u] {
      k = MaxInt(j - R[u][0], 0)
      if DP[u][j] < 0 { DP[u][j] = DP[u][k] + R[u][1] }
      DP[u][j] = MinInt(DP[u][k] + R[u][1], DP[u][j])
    }
    for _, Adj := range G[u] {
      v, a, b = Adj[0], Adj[1], Adj[2]
      add = false
      for j := range DP[u] {
        if j < a { continue }
        if DP[v][j - a] < 0 {
          DP[v][j - a] = DP[u][j] + b
          add = true
        }
        if DP[u][j] + b < DP[v][j - a] {
          DP[v][j - a] = DP[u][j] + b
          add = true
        }
      }
      if add { Q = append(Q, v) }
    }
  }
  for _, dp := range DP[1:] {
    Write(dp[0])
  }
}

func main() {
  Solve()
  Output()
}

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntVec(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatVec(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}
func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

Measured memory_bytes: 2916