### BUGGY CODE ###

import heapq


n,m,s=map(int,input().split())
#隣接行列[金額,時間]
graph=[[] for i in range(n)]
#銀貨リスト
A=[]
for i in range(m):
    u,v,a,b=map(int,input().split())
    A.append(a)
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

change=[]
for i in range(n):
    c,d=map(int,input().split())
    change.append((c,d))

A_max=max(A)
max_money=(n-1)*A_max

s=min(s,max_money)

width=max_money+1
N=n*width
#新しい隣接リスト;(時間,行き先)
system=[[] for i in range(N)]
for index in range(N):
    #頂点
    city=index//width
    #持ち金
    money=index%width

    #頂点の移動
    for next in graph[city]:
        #移動可能か
        if money>=next[1]:
            next_index=next[0]*width+(money-next[1])
            system[index].append((next[2],next_index))

    #持ち金の移動
    add=change[city][0]
    up=1
    while money+add<=max_money:
        system[index].append((change[city][1]*up,index+add))
        add+=change[city][0]
        up+=1
    

def dijkstra_heap(s,n,edge):
    #重みのオーダーでscaleは変更せよ
    scale=10**6

    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*scale+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(scale)]:
            continue
        v = minedge%(scale)
        d[v] = minedge//(scale)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(scale)+e[1])
    return d


D=dijkstra_heap(s,N,system)
for i in range(1,n):
    ans=float('inf')
    for index in range(i*width,(i+1)*width):
        ans=min(ans,D[index])

    print(ans)


### FIXED CODE ###

import heapq


n,m,s=map(int,input().split())
#隣接行列[金額,時間]
graph=[[] for i in range(n)]
#銀貨リスト
A=[]
for i in range(m):
    u,v,a,b=map(int,input().split())
    A.append(a)
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

change=[]
for i in range(n):
    c,d=map(int,input().split())
    change.append((c,d))

A_max=max(A)
max_money=(n-1)*A_max

s=min(s,max_money)

width=max_money+1
N=n*width
#新しい隣接リスト;(時間,行き先)
system=[[] for i in range(N)]
for index in range(N):
    #頂点
    city=index//width
    #持ち金
    money=index%width

    #頂点の移動
    for next in graph[city]:
        #移動可能か
        if money>=next[1]:
            next_index=next[0]*width+(money-next[1])
            system[index].append((next[2],next_index))

    #持ち金の移動(最大n*A_max回かかる)→1回分でよい
    if money+change[city][0]<max_money:
        system[index].append((change[city][1],index+change[city][0]))
    else:
        system[index].append((change[city][1],max_money))


def dijkstra_heap(s,n,edge):
    #頂点数のオーダーでscaleは変更せよ
    scale=10**6

    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*scale+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(scale)]:
            continue
        v = minedge%(scale)
        d[v] = minedge//(scale)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*scale+e[1])
    return d


D=dijkstra_heap(s,N,system)
for i in range(1,n):
    ans=float('inf')
    for index in range(i*width,(i+1)*width):
        ans=min(ans,D[index])

    print(ans)