def main():

    import heapq

    

    def dijkstra(graph,start,cd,s):

        dist = [[float("inf")]*2505 for _ in range(n)]

        q = []

        dist[start][s] = 0

        heapq.heappush(q, (0,start,s))

        

        while q:

            cost, cur_node,coin = heapq.heappop(q)

            

            if dist[cur_node][coin] < cost:

                continue

            

            for nex_node,nex_cost,nex_time  in graph[cur_node]:

                if coin >= nex_cost and dist[nex_node][coin-nex_cost] > cost+nex_time:

                    dist[nex_node][coin-nex_cost] = cost+nex_time

                    heapq.heappush(q, (cost+nex_time,nex_node,coin-nex_cost))

            if dist[cur_node][min(2500,coin+cd[cur_node][0])] > cost+cd[cur_node][1]:

                 dist[cur_node][min(2500,coin+cd[cur_node][0])] = cost+cd[cur_node][1]

                 heapq.heappush(q,(cost+cd[cur_node][1],cur_node,min(2500,coin+cd[cur_node][0])))

                    

        for i in dist[1:]:

            print((min(i)))

    n,m,s = list(map(int,input().split()))

    E = [[] for i in range(n)]

    la = []

    for i in range(m):

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

        u -= 1

        v-= 1

        la.append(a)

        E[u].append((v,a,b))

        E[v].append((u,a,b))



    cd = [list(map(int,input().split())) for i in range(n)]



    dijkstra(E,0,cd,min(s,2500))

if __name__ == "__main__":

    main()
def main():

    import heapq

    

    def dijkstra(graph,s,cd,c):

        dist = [[float("inf")]*2505 for _ in range(n)]

        q = []

        dist[s][c] = 0

        heapq.heappush(q, (0,s,c))

        

        while q:

            d, p,c = heapq.heappop(q)

            

            if dist[p][c] < d:

                continue

            

            for nn,nc,nt  in graph[p]:

                if c >= nc and dist[nn][c-nc] >   d+nt:

                    dist[nn][c-nc] =    d+nt

                    heapq.heappush(q,(d+nt,nn,c-nc))

            if c+cd[p][0] < 2500:

                if dist[p][c+cd[p][0]] >  d+cd[p][1]:

                    dist[p][c+cd[p][0]] = d+cd[p][1]

                    heapq.heappush(q, (d+cd[p][1],p,c+cd[p][0]))

            else:

                if dist[p][2500] >  d+cd[p][1]:

                    dist[p][2500] = d+cd[p][1]

                    heapq.heappush(q, (d+cd[p][1],p,2500))

                    

        for i in dist[1:]:

            print((min(i)))

    n,m,s = list(map(int,input().split()))

    E = [[] for i in range(n)]

    la = []

    for i in range(m):

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

        u -= 1

        v-= 1

        la.append(a)

        E[u].append((v,a,b))

        E[v].append((u,a,b))



    cd = [list(map(int,input().split())) for i in range(n)]



    dijkstra(E,0,cd,min(s,2500))

if __name__ == "__main__":

    main()
def main():
    import heapq

    def dijkstra(graph, start, cd, s):
        dist = [[float("inf")] * 2505 for _ in range(n)]
        q = []
        dist[start][s] = 0
        heapq.heappush(q, (0, start, s))
        while q:
            cost, cur_node, coin = heapq.heappop(q)
            if dist[cur_node][coin] < cost:
                continue
            for nex_node, nex_cost, nex_time in graph[cur_node]:
                if (
                    coin >= nex_cost
                    and dist[nex_node][coin - nex_cost] > cost + nex_time
                ):
                    dist[nex_node][coin - nex_cost] = cost + nex_time
                    heapq.heappush(q, (cost + nex_time, nex_node, coin - nex_cost))
            if (
                dist[cur_node][min(2500, coin + cd[cur_node][0])]
                > cost + cd[cur_node][1]
            ):
                dist[cur_node][min(2500, coin + cd[cur_node][0])] = (
                    cost + cd[cur_node][1]
                )
                heapq.heappush(
                    q,
                    (
                        cost + cd[cur_node][1],
                        cur_node,
                        min(2500, coin + cd[cur_node][0]),
                    ),
                )
        for i in dist[1:]:
            print((min(i)))

    n, m, s = list(map(int, input().split()))
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        la.append(a)
        E[u].append((v, a, b))
        E[v].append((u, a, b))
    cd = [list(map(int, input().split())) for i in range(n)]
    dijkstra(E, 0, cd, min(s, 2500))


if __name__ == "__main__":
    main()

def main():
    import heapq

    def dijkstra(graph, s, cd, c):
        dist = [[float("inf")] * 2505 for _ in range(n)]
        q = []
        dist[s][c] = 0
        heapq.heappush(q, (0, s, c))
        while q:
            d, p, c = heapq.heappop(q)
            if dist[p][c] < d:
                continue
            for nn, nc, nt in graph[p]:
                if c >= nc and dist[nn][c - nc] > d + nt:
                    dist[nn][c - nc] = d + nt
                    heapq.heappush(q, (d + nt, nn, c - nc))
            if c + cd[p][0] < 2500:
                if dist[p][c + cd[p][0]] > d + cd[p][1]:
                    dist[p][c + cd[p][0]] = d + cd[p][1]
                    heapq.heappush(q, (d + cd[p][1], p, c + cd[p][0]))
            else:
                if dist[p][2500] > d + cd[p][1]:
                    dist[p][2500] = d + cd[p][1]
                    heapq.heappush(q, (d + cd[p][1], p, 2500))
        for i in dist[1:]:
            print((min(i)))

    n, m, s = list(map(int, input().split()))
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        la.append(a)
        E[u].append((v, a, b))
        E[v].append((u, a, b))
    cd = [list(map(int, input().split())) for i in range(n)]
    dijkstra(E, 0, cd, min(s, 2500))


if __name__ == "__main__":
    main()

-    def dijkstra(graph, start, cd, s): +    def dijkstra(graph, s, cd, c): -        dist[start][s] = 0 -        heapq.heappush(q, (0, start, s)) +        dist[s][c] = 0 +        heapq.heappush(q, (0, s, c)) -            cost, cur_node, coin = heapq.heappop(q) -            if dist[cur_node][coin] < cost: +            d, p, c = heapq.heappop(q) +            if dist[p][c] < d: -            for nex_node, nex_cost, nex_time in graph[cur_node]: -                if ( -                    coin >= nex_cost -                    and dist[nex_node][coin - nex_cost] > cost + nex_time -                ): -                    dist[nex_node][coin - nex_cost] = cost + nex_time -                    heapq.heappush(q, (cost + nex_time, nex_node, coin - nex_cost)) -            if ( -                dist[cur_node][min(2500, coin + cd[cur_node][0])] -                > cost + cd[cur_node][1] -            ): -                dist[cur_node][min(2500, coin + cd[cur_node][0])] = ( -                    cost + cd[cur_node][1] -                ) -                heapq.heappush( -                    q, -                    ( -                        cost + cd[cur_node][1], -                        cur_node, -                        min(2500, coin + cd[cur_node][0]), -                    ), -                ) +            for nn, nc, nt in graph[p]: +                if c >= nc and dist[nn][c - nc] > d + nt: +                    dist[nn][c - nc] = d + nt +                    heapq.heappush(q, (d + nt, nn, c - nc)) +            if c + cd[p][0] < 2500: +                if dist[p][c + cd[p][0]] > d + cd[p][1]: +                    dist[p][c + cd[p][0]] = d + cd[p][1] +                    heapq.heappush(q, (d + cd[p][1], p, c + cd[p][0])) +            else: +                if dist[p][2500] > d + cd[p][1]: +                    dist[p][2500] = d + cd[p][1] +                    heapq.heappush(q, (d + cd[p][1], p, 2500))