import heapq
N,M,S = [int(i) for i in input().split()]
Train = [[] for p in range(N)]
for j in range(M):
    U,V,A,B = [int(hoge) for hoge in input().split()]
    Train[U-1].append((V-1,(A,B)))#(次、(運賃,時間))
    Train[V-1].append((U-1,(A,B)))

CD = [[int(hoge) for hoge in input().split()] for k in range(N)]

num = N*2501          # グラフのノード数
dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
    
start = 0 * 2501 + S
dist[start] = 0 #ID = Point * 2501 + Money(P=ID//2501 M = ID%2501)
q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, start)) # 始点をpush
while len(q) != 0:
    prov_cost, src = heapq.heappop(q) # pop(仮の距離,ID)
    
    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if dist[src] < prov_cost:
        continue

    # 他の頂点の探索
    src_Point = src//2501
    src_Money = src%2501
    src_RyogaeM = CD[src_Point][0]
    src_RyogaeTime = CD[src_Point][1]

    RyogaeAfter = min(2500,src_Money + src_RyogaeM)
    RyogaeID = src - src_Money + RyogaeAfter
    cost = src_RyogaeTime

    if dist[RyogaeID] > dist[src] + cost:
        dist[RyogaeID] = dist[src] + cost#distの更新
        heapq.heappush(q,(dist[RyogaeID],RyogaeID))

    for togo,trainfo in Train[src//2501]:#つながってる線路について
        cost = trainfo[1]#src→dest間の距離
        fee = trainfo[0]
        dest = togo * 2501 + src_Money - fee
        if src_Money >= fee and dist[dest] > dist[src] + cost:
            dist[dest] = dist[src] + cost # distの更新
            heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
            prev[dest] = src                      # 前の頂点を記録

curpoint = 0
TheEnd = 2500
curmin = float("inf")
for point,d in enumerate(dist):
    if d < curmin:
        curmin = d
    if point == TheEnd:
        TheEnd += 2501
        if point > 2500:
            print(curmin)
        curmin = float("inf")



### FIXED CODE ###

import heapq
N,M,S = [int(i) for i in input().split()]
S = min(S,2500)
Train = [[] for p in range(N)]
for j in range(M):
    U,V,A,B = [int(hoge) for hoge in input().split()]
    Train[U-1].append((V-1,(A,B)))#(次、(運賃,時間))
    Train[V-1].append((U-1,(A,B)))

CD = [[int(hoge) for hoge in input().split()] for k in range(N)]

num = N*2501          # グラフのノード数
dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
    
start = 0 * 2501 + S
dist[start] = 0 #ID = Point * 2501 + Money(P=ID//2501 M = ID%2501)
q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, start)) # 始点をpush
while len(q) != 0:
    prov_cost, src = heapq.heappop(q) # pop(仮の距離,ID)
    
    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if dist[src] < prov_cost:
        continue

    # 他の頂点の探索
    src_Point = src//2501
    src_Money = src%2501
    src_RyogaeM = CD[src_Point][0]
    src_RyogaeTime = CD[src_Point][1]

    RyogaeAfter = min(2500,src_Money + src_RyogaeM)
    RyogaeID = src - src_Money + RyogaeAfter
    cost = src_RyogaeTime

    if dist[RyogaeID] > dist[src] + cost:
        dist[RyogaeID] = dist[src] + cost#distの更新
        heapq.heappush(q,(dist[RyogaeID],RyogaeID))

    for togo,trainfo in Train[src//2501]:#つながってる線路について
        cost = trainfo[1]#src→dest間の距離
        fee = trainfo[0]
        dest = togo * 2501 + src_Money - fee
        if src_Money >= fee and dist[dest] > dist[src] + cost:
            dist[dest] = dist[src] + cost # distの更新
            heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
            prev[dest] = src                      # 前の頂点を記録

curpoint = 0
TheEnd = 2500
curmin = float("inf")
for point,d in enumerate(dist):
    if d < curmin:
        curmin = d
    if point == TheEnd:
        TheEnd += 2501
        if point > 2500:
            print(curmin)
        curmin = float("inf")