# Original solution
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

class RMQ:
    def __init__(self, size):
        n = 1
        while n < size:
            n <<= 1
        self.n = n
        self.data = [float('inf')] * (2*n-1)
        self.ix = [-1] * (2*n-1)

    # change the value of the ith element to x
    def update(self, i, x):
        i += self.n-1  # the leaf
        self.data[i] = x
        self.ix[i] = i-(self.n-1)
        while i > 0:
            i = (i-1)//2
            vl = self.data[i*2+1]
            vr = self.data[i*2+2]
            if vl < vr:
                self.data[i] = vl
                self.ix[i] = self.ix[i*2+1]
            else:
                self.data[i] = vr
                self.ix[i] = self.ix[i*2+2]

    # return the minimum value in the range [a, b)
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.n)

    # i is the index of the node, and it corresponds to the range [l, r)
    def _query(self, a, b, i, l, r):
        if r == -1:
            r = self.n

        # if no overlap
        if r <= a or b <= l:
            return float('inf')

        # if [a, b) contains whole [l, r)
        if a <= l and r <= b:
            return self.data[i]

        m = (l+r)//2
        vl = self._query(a, b, i*2+1, l, m)
        vr = self._query(a, b, i*2+2, m, r)
        return min(vl, vr)

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = list(map(int, input().split()))
    MAX = 10001
    AB = [[None] * N for _ in range(N)]
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    rmq = RMQ(N*MAX)
    for i in range(N*MAX):
        rmq.update(i, dist[i])
    for v in range(1, N):
        print((rmq.query(v*MAX, (v+1)*MAX)))

main()

# Optimized solution
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = list(map(int, input().split()))
    AB = [[None] * N for _ in range(N)]
    s = 0
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
        s += A
    MAX = s + 1
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    for v in range(1, N):
        print((min(dist[v*MAX:(v+1)*MAX])))
main()