import Foundation

private struct PriorityQueue<T: Comparable> {
    private var data: [T]
    
    public var isEmpty: Bool {
        return data.isEmpty
    }
    
    public var count: Int {
        return data.count
    }
    
    init() {
        data = []
    }
    
    public mutating func pop() -> T? {
        return data.popLast().map { item in
            var item = item
            if !isEmpty {
                swap(&item, &data[0])
                siftDown()
            }
            return item
        }
    }
    
    public mutating func append(_ item: T) {
        let oldLen = self.count
        self.data.append(item)
        self.siftUp(oldLen)
    }
    
    private mutating func siftDown() {
        var pos = 0
        let end = count
        
        data.withUnsafeMutableBufferPointer { bufferPointer in
            let _data = bufferPointer.baseAddress!
            swap(&_data[0], &_data[end])
            
            var child = 2 * pos + 1
            while child < end {
                let right = child + 1
                if right < end && _data[child] <= _data[right] {
                    child = right
                }
                swap(&_data[pos], &_data[child])
                pos = child
                child = 2 * pos + 1
            }
        }

        siftUp(pos)
    }
    
    private mutating func siftUp(_ pos: Int) {
        var pos = pos
        while pos > 0 {
            let parent = (pos - 1) / 2;
            if data[pos] <= data[parent] {
                break
            }
            pos = parent
            data[pos] = data[parent]
        }
    }
}


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

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

struct Node: Comparable {
    static func < (lhs: Node, rhs: Node) -> Bool {
        return (-lhs.dist, lhs.money, lhs.n) < (-rhs.dist, rhs.money, rhs.n)
    }
    
    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 = Array<[(Int, fare: Int, dist: Int)]>(repeating: [], count: N)
    for _ in (1...M) {
        let uvab = readInt()
        let u = uvab[0] - 1
        let v = uvab[1] - 1
        let a = uvab[2]
        let b = uvab[3]
        maxFare = max(maxFare, a)

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

        graph[i].append((i, fare: -c, dist: d))
    }

    maxFare *= (N-1)

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

    var pq = PriorityQueue<Node>()
    pq.append(Node(0, 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.append(Node(v, rest, uNode.dist + dist))
            }
        }
    }
    
    for i in 1..<N {
        print(dists[i].min()!)
    }
}

practice()


Measured memory_bytes: 19988