class Dijkstra():

    """ ダイクストラ法

    重み付きグラフにおける単一始点最短路アルゴリズム



    * 使用条件

        - 負のコストがないこと

        - 有向グラフ、無向グラフともにOK



    * 計算量はO(E*log(V))



    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい

    """

    class Edge():

        """ 重み付き有向辺 """

        def __init__(self, _to, _cost):

            self.to = _to

            self.cost = _cost



    def __init__(self, V):

        """ 重み付き有向辺

        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい



        Args:

            V(int): 頂点の数

        """

        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺

        self._E = 0  # 辺の数

        self._V = V  # 頂点の数



    @property

    def E(self):

        """ 辺数

        無向グラフのときは、辺数は有向グラフの倍になる

        """

        return self._E



    @property

    def V(self):

        """ 頂点数 """

        return self._V



    def add(self, _from, _to, _cost):

        """ 2頂点と、辺のコストを追加する """

        self.G[_from].append(self.Edge(_to, _cost))

        self._E += 1



    def shortest_path(self, s):

        """ 始点sから頂点iまでの最短路を格納したリストを返す

        Args:

            s(int): 始点s

        Returns:

            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。

                     到達不可の場合、値はfloat("inf")

        """

        import heapq

        que = []  # プライオリティキュー（ヒープ木）

        d = [float("inf")] * self.V

        d[s] = 0

        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する



        while len(que) != 0:

            cost, v = heapq.heappop(que)

            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ

            if d[v] < cost: continue



            for i in range(len(self.G[v])):

                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する

                e = self.G[v][i]  # vのi個目の隣接辺e

                if d[e.to] > d[v] + e.cost:

                    d[e.to] = d[v] + e.cost  # dの更新

                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush

        return d



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

pro=Dijkstra(N*5001)

for i in range(0,M):

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

    for j in range(a,5001):

        pro.add(N*j+u-1,N*(j-a)+v-1,b)

        pro.add(N*j+v-1,N*(j-a)+u-1,b)



for i in range(0,N):

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

    for j in range(0,5000):

        to=min(5000,j+c)

        pro.add(N*j+i,N*to+i,d)



S=min(5000,S)

ans=pro.shortest_path(N*S)

for i in range(1,N):

    p=float("inf")

    for j in range(0,5001):

        p=min(p,ans[N*j+i])

    print(p)
class Dijkstra():

    """ ダイクストラ法

    重み付きグラフにおける単一始点最短路アルゴリズム



    * 使用条件

        - 負のコストがないこと

        - 有向グラフ、無向グラフともにOK



    * 計算量はO(E*log(V))



    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい

    """

    class Edge():

        """ 重み付き有向辺 """

        def __init__(self, _to, _cost):

            self.to = _to

            self.cost = _cost



    def __init__(self, V):

        """ 重み付き有向辺

        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい



        Args:

            V(int): 頂点の数

        """

        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺

        self._E = 0  # 辺の数

        self._V = V  # 頂点の数



    @property

    def E(self):

        """ 辺数

        無向グラフのときは、辺数は有向グラフの倍になる

        """

        return self._E



    @property

    def V(self):

        """ 頂点数 """

        return self._V



    def add(self, _from, _to, _cost):

        """ 2頂点と、辺のコストを追加する """

        self.G[_from].append(self.Edge(_to, _cost))

        self._E += 1



    def shortest_path(self, s):

        """ 始点sから頂点iまでの最短路を格納したリストを返す

        Args:

            s(int): 始点s

        Returns:

            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。

                     到達不可の場合、値はfloat("inf")

        """

        import heapq

        que = []  # プライオリティキュー（ヒープ木）

        d = [float("inf")] * self.V

        d[s] = 0

        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する



        while len(que) != 0:

            cost, v = heapq.heappop(que)

            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ

            if d[v] < cost: continue



            for i in range(len(self.G[v])):

                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する

                e = self.G[v][i]  # vのi個目の隣接辺e

                if d[e.to] > d[v] + e.cost:

                    d[e.to] = d[v] + e.cost  # dの更新

                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush

        return d



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

pro=Dijkstra(N*(50*(N-1)+1))

for i in range(0,M):

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

    for j in range(a,50*(N-1)+1):

        pro.add(N*j+u-1,N*(j-a)+v-1,b)

        pro.add(N*j+v-1,N*(j-a)+u-1,b)



for i in range(0,N):

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

    for j in range(0,50*(N-1)):

        to=min(50*(N-1),j+c)

        pro.add(N*j+i,N*to+i,d)



S=min(50*(N-1),S)

ans=pro.shortest_path(N*S)

for i in range(1,N):

    p=float("inf")

    for j in range(0,50*(N-1)+1):

        p=min(p,ans[N*j+i])

    print(p)

class Dijkstra:
    """ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム
    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    * 計算量はO(E*log(V))
    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """

    class Edge:
        """重み付き有向辺"""

        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい
        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """頂点数"""
        return self._V

    def add(self, _from, _to, _cost):
        """2頂点と、辺のコストを追加する"""
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq

        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する
        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost:
                continue
            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(
                        que, (d[e.to], e.to)
                    )  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d


N, M, S = list(map(int, input().split()))
pro = Dijkstra(N * 5001)
for i in range(0, M):
    u, v, a, b = list(map(int, input().split()))
    for j in range(a, 5001):
        pro.add(N * j + u - 1, N * (j - a) + v - 1, b)
        pro.add(N * j + v - 1, N * (j - a) + u - 1, b)
for i in range(0, N):
    c, d = list(map(int, input().split()))
    for j in range(0, 5000):
        to = min(5000, j + c)
        pro.add(N * j + i, N * to + i, d)
S = min(5000, S)
ans = pro.shortest_path(N * S)
for i in range(1, N):
    p = float("inf")
    for j in range(0, 5001):
        p = min(p, ans[N * j + i])
    print(p)

class Dijkstra:
    """ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム
    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    * 計算量はO(E*log(V))
    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """

    class Edge:
        """重み付き有向辺"""

        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい
        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """頂点数"""
        return self._V

    def add(self, _from, _to, _cost):
        """2頂点と、辺のコストを追加する"""
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq

        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する
        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost:
                continue
            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(
                        que, (d[e.to], e.to)
                    )  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d


N, M, S = list(map(int, input().split()))
pro = Dijkstra(N * (50 * (N - 1) + 1))
for i in range(0, M):
    u, v, a, b = list(map(int, input().split()))
    for j in range(a, 50 * (N - 1) + 1):
        pro.add(N * j + u - 1, N * (j - a) + v - 1, b)
        pro.add(N * j + v - 1, N * (j - a) + u - 1, b)
for i in range(0, N):
    c, d = list(map(int, input().split()))
    for j in range(0, 50 * (N - 1)):
        to = min(50 * (N - 1), j + c)
        pro.add(N * j + i, N * to + i, d)
S = min(50 * (N - 1), S)
ans = pro.shortest_path(N * S)
for i in range(1, N):
    p = float("inf")
    for j in range(0, 50 * (N - 1) + 1):
        p = min(p, ans[N * j + i])
    print(p)

-pro = Dijkstra(N * 5001) +pro = Dijkstra(N * (50 * (N - 1) + 1)) -    for j in range(a, 5001): +    for j in range(a, 50 * (N - 1) + 1): -    for j in range(0, 5000): -        to = min(5000, j + c) +    for j in range(0, 50 * (N - 1)): +        to = min(50 * (N - 1), j + c) -S = min(5000, S) +S = min(50 * (N - 1), S) -    for j in range(0, 5001): +    for j in range(0, 50 * (N - 1) + 1):