import Foundation

// by: https://github.com/davecom/SwiftPriorityQueue.git
private struct PriorityQueue<T: Comparable> {
    
    fileprivate var heap = [T]()
    private let ordered: (T, T) -> Bool
    
    init(ascending: Bool = false, startingValues: [T] = []) {
        self.init(order: ascending ? { $0 > $1 } : { $0 < $1 }, startingValues: startingValues)
    }
    
    init(order: @escaping (T, T) -> Bool, startingValues: [T] = []) {
        ordered = order
        
        heap = startingValues
        var i = heap.count/2 - 1
        while i >= 0 {
            sink(i)
            i -= 1
        }
    }
    
    var count: Int { return heap.count }
    
    var isEmpty: Bool { return heap.isEmpty }

    mutating func push(_ element: T) {
        heap.append(element)
        swim(heap.count - 1)
    }
    
    mutating func pop() -> T? {
        
        if heap.isEmpty { return nil }
        let count = heap.count
        if count == 1 { return heap.removeFirst() }
        fastPop(newCount: count - 1)
        
        return heap.removeLast()
    }
    
    mutating func remove(_ item: T) {
        if let index = heap.firstIndex(of: item) {
            heap.swapAt(index, heap.count - 1)
            heap.removeLast()
            if index < heap.count {
                swim(index)
                sink(index)
            }
        }
    }
    
    mutating func removeAll(_ item: T) {
        var lastCount = heap.count
        remove(item)
        while (heap.count < lastCount) {
            lastCount = heap.count
            remove(item)
        }
    }
    

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

    mutating func clear() {
        heap.removeAll(keepingCapacity: false)
    }

    private mutating func sink(_ index: Int) {
        var index = index
        while 2 * index + 1 < heap.count {
            
            var j = 2 * index + 1
            
            if j < (heap.count - 1) && ordered(heap[j], heap[j + 1]) { j += 1 }
            if !ordered(heap[index], heap[j]) { break }
            
            heap.swapAt(index, j)
            index = j
        }
    }

    private mutating func fastPop(newCount: Int) {
        var index = 0
        heap.withUnsafeMutableBufferPointer { bufferPointer in
            let _heap = bufferPointer.baseAddress!
            swap(&_heap[0], &_heap[newCount])
            while 2 * index + 1 < newCount {
                var j = 2 * index + 1
                if j < (newCount - 1) && ordered(_heap[j], _heap[j+1]) { j += 1 }
                if !ordered(_heap[index], _heap[j]) { return }
                swap(&_heap[index], &_heap[j])
                index = j
            }
        }
    }
    
    private mutating func swim(_ index: Int) {
        var index = index
        while index > 0 && ordered(heap[(index - 1) / 2], heap[index]) {
            heap.swapAt((index - 1) / 2, index)
            index = (index - 1) / 2
        }
    }
}

// MARK: - GeneratorType
extension PriorityQueue: IteratorProtocol {
    
    typealias Element = T
    mutating func next() -> Element? { return pop() }
}

// MARK: - SequenceType
extension PriorityQueue: Sequence {
    
    typealias Iterator = PriorityQueue
    func makeIterator() -> Iterator { return self }
}

// MARK: - CollectionType
extension PriorityQueue: Collection {
    
    typealias Index = Int
    
    var startIndex: Int { return heap.startIndex }
    var endIndex: Int { return heap.endIndex }
    
    subscript(i: Int) -> T { return heap[i] }
    
    func index(after i: PriorityQueue.Index) -> PriorityQueue.Index {
        return heap.index(after: i)
    }
}

// MARK: - CustomStringConvertible, CustomDebugStringConvertible
extension PriorityQueue: CustomStringConvertible, CustomDebugStringConvertible {
    
    var description: String { return heap.description }
    var debugDescription: String { return heap.debugDescription }
}

// ------------------------

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

struct Node: Comparable {
    static func < (lhs: Node, rhs: Node) -> Bool {
        if lhs.dist < rhs.dist {
            return lhs.money < rhs.money
        } else {
            return false
        }
    }
    
    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 practice() {
    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 = PriorityQueue<Node>(order: <)
    pq.push(Node(1, S, 0))
    while let uNode = pq.pop() {
        for (v, (fare, dist)) in graph[uNode.n]! {
            let rest = min(maxFare, uNode.money - fare)
            if rest >= 0 && dists[v][rest] > uNode.dist + dist {
                dists[v][rest] = uNode.dist + dist
                pq.push(Node(v, rest, uNode.dist + dist))
            }
        }
    }

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

practice()

