import Foundation

struct Heap<T> {
  
  var nodes = [T]()
 
  private var orderCriteria: (T, T) -> Bool

   init(sort: @escaping (T, T) -> Bool) {
    self.orderCriteria = sort
  }

   init(array: [T], sort: @escaping (T, T) -> Bool) {
    self.orderCriteria = sort
    configureHeap(from: array)
  }
  
  private mutating func configureHeap(from array: [T]) {
    nodes = array
    for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
      shiftDown(i)
    }
  }
  
   var isEmpty: Bool {
    return nodes.isEmpty
  }
  
   var count: Int {
    return nodes.count
  }
  
  @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
    return (i - 1) / 2
  }

  @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
    return 2*i + 1
  }

  @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
    return 2*i + 2
  }

   func peek() -> T? {
    return nodes.first
  }
  

   mutating func insert(_ value: T) {
    nodes.append(value)
    shiftUp(nodes.count - 1)
  }
  
   mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
    for value in sequence {
      insert(value)
    }
  }

   mutating func replace(index i: Int, value: T) {
    guard i < nodes.count else { return }
    
    remove(at: i)
    insert(value)
  }
 
  @discardableResult  mutating func remove() -> T? {
    guard !nodes.isEmpty else { return nil }
    
    if nodes.count == 1 {
      return nodes.removeLast()
    } else {
      let value = nodes[0]
      nodes[0] = nodes.removeLast()
      shiftDown(0)
      return value
    }
  }

  @discardableResult  mutating func remove(at index: Int) -> T? {
    guard index < nodes.count else { return nil }
    
    let size = nodes.count - 1
    if index != size {
      nodes.swapAt(index, size)
      shiftDown(from: index, until: size)
      shiftUp(index)
    }
    return nodes.removeLast()
  }

  internal mutating func shiftUp(_ index: Int) {
    var childIndex = index
    let child = nodes[childIndex]
    var parentIndex = self.parentIndex(ofIndex: childIndex)
    
    while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
      nodes[childIndex] = nodes[parentIndex]
      childIndex = parentIndex
      parentIndex = self.parentIndex(ofIndex: childIndex)
    }
    
    nodes[childIndex] = child
  }

  internal mutating func shiftDown(from index: Int, until endIndex: Int) {
    let leftChildIndex = self.leftChildIndex(ofIndex: index)
    let rightChildIndex = leftChildIndex + 1

    var first = index
    if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
      first = leftChildIndex
    }
    if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
      first = rightChildIndex
    }
    if first == index { return }
    
    nodes.swapAt(index, first)
    shiftDown(from: first, until: endIndex)
  }
  
  internal mutating func shiftDown(_ index: Int) {
    shiftDown(from: index, until: nodes.count)
  }
  
}

extension Heap where T: Equatable {
  
   func firstIndex(of node: T) -> Int? {
    return nodes.firstIndex(where: { $0 == node })
  }
  
  @discardableResult  mutating func remove(node: T) -> T? {
    if let index = firstIndex(of: node) {
      return remove(at: index)
    }
    return nil
  }
  
}

func readInt() -> [Int] {
    return readLine()!.split(separator: " ").map { c in Int(c)! }
}

struct Node {
    let n: Int
    let money: Int
    let dist: Int
    init(_ n: Int, _ money: Int, _ dist: Int) {
        self.n = n
        self.money = money
        self.dist = dist
    }    
}

func main() {
    let line = readInt()
    let N = line[0]
    let M = line[1]
    let S = line[2]

    var maxFare = 0
    var graph = [Int: [Int: (fare: Int, dist: Int)]]()
    for i in (1...N) {
        graph[i] = [:]
    }
    for _ in (1...M) {
        let uvab = readInt()
        let u = uvab[0]
        let v = uvab[1]
        let a = uvab[2]
        let b = uvab[3]
        maxFare = max(maxFare, a)

        graph[u]![v] = (fare: a, dist: b)
        graph[v]![u] = (fare: a, dist: b)
    }
    for i in (1...N) {
        let cd = readInt()
        let c = cd[0]
        let d = cd[1]

        graph[i]![i] = (fare: -c, dist: d)
    }

    maxFare *= (N-1)

    var dists = (0...N).map {_ in Array(repeating: Int.max, count: maxFare+1)}
    dists[1][0] = 0

    var pq = Heap<Node>(sort: {
        if $0.dist < $1.dist {
            return $0.money < $1.money
        } else {
            return false
        }
    })
    pq.insert(Node(1, S, 0))
    while let uNode = pq.remove() {
        for (v, (fare, dist)) in graph[uNode.n]! {
            let rest = min(maxFare, uNode.money - fare)
            if rest >= 0 && (dists[v][rest] == Int.max || dists[v][rest] > uNode.dist + dist) {
                dists[v][rest] = uNode.dist + dist
                pq.insert(Node(v, rest, uNode.dist + dist))
            } 
        }
    }

    for dist in dists[2...] {
        print(dist.min()!)
    }
}

main()



Measured memory_bytes: 21608