def main():

    import dataclasses

    from heapq import heappush, heappop



    @dataclasses.dataclass(frozen=True)

    class Path:

        to: int

        fare: int

        travel_time: int



    @dataclasses.dataclass(frozen=True)

    class ExchangeRate:

        Ag: int

        exchange_time: int



    @dataclasses.dataclass(frozen=True)

    class Traveler:

        consumption_time: int

        remaining_Ag: int

        location: int



        def __gt__(self, other):

            return self.consumption_time > other.consumption_time



        def __eq__(self, other):

            return self.consumption_time == other.consumption_time



    INF = 1 << 60

    MX_AG = 2500



    N, M, S = list(map(int, input().split()))

    S = min(S, MX_AG)  # それ以上のAgは不要



    g = tuple(set() for _ in range(N))

    for _ in range(M):

        u, v, a, b = list(map(int, input().split()))

        u -= 1

        v -= 1

        g[u].add(Path(v, a, b))

        g[v].add(Path(u, a, b))



    exchange = []

    for _ in range(N):

        c, d = list(map(int, input().split()))

        exchange.append(ExchangeRate(c, d))



    h = [Traveler(0, S, 0)]



    time = [[INF] * (MX_AG + 1) for _ in range(N)]

    time[0][S] = 0

    # time[location][r_Ag]:=minimum_time_to_reach



    while h:

        t = heappop(h)

        for p in g[t.location]:

            n_Ag = t.remaining_Ag - p.fare

            if n_Ag < 0: continue

            cf = time[p.to][n_Ag]

            n_time = t.consumption_time + p.travel_time

            if cf <= n_time: continue

            time[p.to][n_Ag] = n_time

            heappush(h, Traveler(consumption_time=n_time, remaining_Ag=n_Ag, location=p.to))



        e_time = t.consumption_time + exchange[t.location].exchange_time

        e_Ag = t.remaining_Ag + exchange[t.location].Ag

        if e_Ag > MX_AG: continue

        cf = time[t.location][e_Ag]

        if cf <= e_time: continue

        time[t.location][e_Ag] = e_time

        heappush(h, Traveler(consumption_time=e_time, remaining_Ag=e_Ag, location=t.location))



    for to in range(1, N):

        print((min(time[to])))





if __name__ == '__main__':

    main()

def main():

    from heapq import heappush, heappop



    INF = 1 << 60

    MX_AG = 2500



    N, M, S = list(map(int, input().split()))

    S = min(S, MX_AG)  # それ以上のAgは不要



    g = tuple(set() for _ in range(N))

    for _ in range(M):

        u, v, a, b = list(map(int, input().split()))

        u -= 1

        v -= 1

        g[u].add((v, a, b))

        g[v].add((u, a, b))



    exchange = []

    for _ in range(N):

        c, d = list(map(int, input().split()))

        exchange.append((c, d))



    h = [(0, S, 0)]



    time = [[INF] * (MX_AG + 1) for _ in range(N)]

    time[0][S] = 0

    # time[location][r_Ag]:=minimum_time_to_reach



    while h:

        t, ag, loc = heappop(h)

        for to, fare, dt in g[loc]:

            n_Ag = ag - fare

            if n_Ag < 0: continue

            cf = time[to][n_Ag]

            n_time = t + dt

            if cf <= n_time: continue

            time[to][n_Ag] = n_time

            heappush(h, (n_time, n_Ag, to))



        e_time = t + exchange[loc][1]

        e_Ag = ag + exchange[loc][0]

        if e_Ag > MX_AG: continue

        cf = time[loc][e_Ag]

        if cf <= e_time: continue

        time[loc][e_Ag] = e_time

        heappush(h, (e_time, e_Ag, loc))



    for to in range(1, N):

        print((min(time[to])))





if __name__ == '__main__':

    main()

def main():
    import dataclasses
    from heapq import heappush, heappop

    @dataclasses.dataclass(frozen=True)
    class Path:
        to: int
        fare: int
        travel_time: int

    @dataclasses.dataclass(frozen=True)
    class ExchangeRate:
        Ag: int
        exchange_time: int

    @dataclasses.dataclass(frozen=True)
    class Traveler:
        consumption_time: int
        remaining_Ag: int
        location: int

        def __gt__(self, other):
            return self.consumption_time > other.consumption_time

        def __eq__(self, other):
            return self.consumption_time == other.consumption_time

    INF = 1 << 60
    MX_AG = 2500
    N, M, S = list(map(int, input().split()))
    S = min(S, MX_AG)  # それ以上のAgは不要
    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        g[u].add(Path(v, a, b))
        g[v].add(Path(u, a, b))
    exchange = []
    for _ in range(N):
        c, d = list(map(int, input().split()))
        exchange.append(ExchangeRate(c, d))
    h = [Traveler(0, S, 0)]
    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    # time[location][r_Ag]:=minimum_time_to_reach
    while h:
        t = heappop(h)
        for p in g[t.location]:
            n_Ag = t.remaining_Ag - p.fare
            if n_Ag < 0:
                continue
            cf = time[p.to][n_Ag]
            n_time = t.consumption_time + p.travel_time
            if cf <= n_time:
                continue
            time[p.to][n_Ag] = n_time
            heappush(
                h, Traveler(consumption_time=n_time, remaining_Ag=n_Ag, location=p.to)
            )
        e_time = t.consumption_time + exchange[t.location].exchange_time
        e_Ag = t.remaining_Ag + exchange[t.location].Ag
        if e_Ag > MX_AG:
            continue
        cf = time[t.location][e_Ag]
        if cf <= e_time:
            continue
        time[t.location][e_Ag] = e_time
        heappush(
            h, Traveler(consumption_time=e_time, remaining_Ag=e_Ag, location=t.location)
        )
    for to in range(1, N):
        print((min(time[to])))


if __name__ == "__main__":
    main()

def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500
    N, M, S = list(map(int, input().split()))
    S = min(S, MX_AG)  # それ以上のAgは不要
    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))
    exchange = []
    for _ in range(N):
        c, d = list(map(int, input().split()))
        exchange.append((c, d))
    h = [(0, S, 0)]
    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    # time[location][r_Ag]:=minimum_time_to_reach
    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            n_Ag = ag - fare
            if n_Ag < 0:
                continue
            cf = time[to][n_Ag]
            n_time = t + dt
            if cf <= n_time:
                continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))
        e_time = t + exchange[loc][1]
        e_Ag = ag + exchange[loc][0]
        if e_Ag > MX_AG:
            continue
        cf = time[loc][e_Ag]
        if cf <= e_time:
            continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))
    for to in range(1, N):
        print((min(time[to])))


if __name__ == "__main__":
    main()

-    import dataclasses - -    @dataclasses.dataclass(frozen=True) -    class Path: -        to: int -        fare: int -        travel_time: int - -    @dataclasses.dataclass(frozen=True) -    class ExchangeRate: -        Ag: int -        exchange_time: int - -    @dataclasses.dataclass(frozen=True) -    class Traveler: -        consumption_time: int -        remaining_Ag: int -        location: int - -        def __gt__(self, other): -            return self.consumption_time > other.consumption_time - -        def __eq__(self, other): -            return self.consumption_time == other.consumption_time -        g[u].add(Path(v, a, b)) -        g[v].add(Path(u, a, b)) +        g[u].add((v, a, b)) +        g[v].add((u, a, b)) -        exchange.append(ExchangeRate(c, d)) -    h = [Traveler(0, S, 0)] +        exchange.append((c, d)) +    h = [(0, S, 0)] -        t = heappop(h) -        for p in g[t.location]: -            n_Ag = t.remaining_Ag - p.fare +        t, ag, loc = heappop(h) +        for to, fare, dt in g[loc]: +            n_Ag = ag - fare -            cf = time[p.to][n_Ag] -            n_time = t.consumption_time + p.travel_time +            cf = time[to][n_Ag] +            n_time = t + dt -            time[p.to][n_Ag] = n_time -            heappush( -                h, Traveler(consumption_time=n_time, remaining_Ag=n_Ag, location=p.to) -            ) -        e_time = t.consumption_time + exchange[t.location].exchange_time -        e_Ag = t.remaining_Ag + exchange[t.location].Ag +            time[to][n_Ag] = n_time +            heappush(h, (n_time, n_Ag, to)) +        e_time = t + exchange[loc][1] +        e_Ag = ag + exchange[loc][0] -        cf = time[t.location][e_Ag] +        cf = time[loc][e_Ag] -        time[t.location][e_Ag] = e_time -        heappush( -            h, Traveler(consumption_time=e_time, remaining_Ag=e_Ag, location=t.location) -        ) +        time[loc][e_Ag] = e_time +        heappush(h, (e_time, e_Ag, loc))