CodeEff/ECCO huggingface dataset:
# Original solution
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline


class Heap():
    def __init__(self, ):
        self.h = []

    def heapify(self, h):
        self.h = h
        heapify(self.h)

    def heappop(self,):
        return heappop(self.h)

    def heappush(self, x):
        heappush(self.h, x)


N, M, S = list(map(int, input().split()))
INF = 10**100
G = [[] for _ in [0]*N]
C = []

for _ in [0]*M:
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    G[v].append((u, a, b))
    G[u].append((v, a, b))

for i in range(N):
    a, b = list(map(int, input().split()))
    C.append((a, b))


def push(t, s, v):
    if s < 0:
        return
    if s >= MAX:
        s = MAX-1
    if dp[v][s] <= t:
        return
    dp[v][s] = t
    heappush(q, (t, s, v))


MAX = 2500
S = min(S, MAX)
dp = [[INF]*MAX for _ in [0]*N]

q = []
push(0, S, 0)

while q:
    t, s, v = heappop(q)
    if dp[v][s] != t:
        continue

    c, d = C[v]
    push(t+d, s+c, v)

    for u, a, b in G[v]:
        push(t+b, s-a, u)

for d in dp[1:]:
    ans = INF
    for s in range(MAX):
        if ans > d[s]:
            ans = d[s]
    print(ans)


# Optimized solution
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
INF = 10**100
MAX = 2500
N, M, S = list(map(int, input().split()))
S = min(S, MAX)
G = [[] for _ in [0]*N]
C = []
for _ in [0]*M:
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    G[v].append((u, a, b))
    G[u].append((v, a, b))

for i in range(N):
    a, b = list(map(int, input().split()))
    C.append((a, b))

# dijkstra
dp = [[INF]*MAX for _ in [0]*N]
q = []
def push(t, s, v):
    if s < 0:
        return
    if s >= MAX:
        s = MAX-1
    if dp[v][s] <= t:
        return
    dp[v][s] = t
    heappush(q, (t, s, v))

push(0, S, 0)

while q:
    t, s, v = heappop(q)
    if dp[v][s] != t:
        continue

    c, d = C[v]
    push(t+d, s+c, v)

    for u, a, b in G[v]:
        push(t+b, s-a, u)

# output
for d in dp[1:]:
    ans = INF
    for s in range(MAX):
        if ans > d[s]:
            ans = d[s]
    print(ans)
# Original solution
import heapq
def dijkstra_heap():
    used = [-1] * (2501*n)
    edgelist=[]
    d=[0]*n
    d[0]=1
    f=1
    for i in range(0,2501):
        if 0<=ss+i*cd[0][0]<=2500:
            heapq.heappush(edgelist,[cd[0][1]*i,cd[0][0]*i+ss])
        else:
            break
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2501
        used[v] = kai
        if d[v//2501]==0:
            d[v//2501]=1
            f+=1
            if f==n:
                return used
        for e in edge[v//2501]:
            if mai-e[1]>=0:
                for i in range(2501):
                    sss=mai-e[1]+cd[e[2]][0]*i
                    if 0<=sss<=2500:
                        if used[e[2]*2501+sss]==-1:
                            heapq.heappush(edgelist,[e[0]+kai+cd[e[2]][1]*i,e[2]*2501+sss])  
                    else:
                        break
    return used

################################
n,m,ss = list(map(int,input().split()))
ss=min(2500,ss)
edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = list(map(int,input().split()))
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2501):
        if pp[i*2501+j]!=-1:
            ans=min(ans,pp[i*2501+j])
    print(ans)

# Optimized solution
import heapq
def dijkstra_heap():
    used = [-1] * (2451*n)
    edgelist=[]
    heapq.heappush(edgelist,[0,ss])
    while len(edgelist):
        #print(len(edgelist))
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2451
        used[v] = kai
        for e in edge[v//2451]:
            if mai-e[1]>=0:
                sss=mai-e[1]
                if used[e[2]*2451+sss]==-1:
                    heapq.heappush(edgelist,[e[0]+kai,e[2]*2451+sss])
        if mai+cd[v//2451][0]<=2450:
            if used[v+cd[v//2451][0]]==-1:
                heapq.heappush(edgelist,[kai+cd[v//2451][1],v+cd[v//2451][0]])
    return used

################################
n,m,ss = list(map(int,input().split()))
ss=min(2450,ss)
edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = list(map(int,input().split()))
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2451):
        if pp[i*2451+j]!=-1:
            ans=min(ans,pp[i*2451+j])
    print(ans)
# Original solution
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

N, M, S = list(map(int, input().split()))
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

sumA = 0
for u, v, a, b in UVAB:
    sumA += a
#print(sumA)

def dijkstra(s, graph) -> list:
    dist = [[INF for _ in range(N + 1)] for _ in range(sumA + 1)]
    dist[s][1] = 0
    hp = []
    heappush(hp, (0, (s, 1)))
    while hp:
        #print(hp)
        t, (i, j) = heappop(hp)
        for dt, (ni, nj) in graph[i][j]:
            if dist[ni][nj] > t + dt:
                dist[ni][nj] = t + dt
                heappush(hp, (dist[ni][nj], (ni, nj)))
    #print("")
    return dist

graph = [[[] for _ in range(N + 1)] for _ in range(sumA + 1)]
# graph[i][j] = [(dt, (ni, nj)), ...]
#都市Ajにいるときに、銀貨をi枚持っている
#この時(i, j)から(ni, nj)への遷移にかかる時間はdt

for j in range(1, N + 1):
    c, d = CD[j - 1]
    for i in range(sumA + 1):
        graph[i][j].append((d, (min(i + c, sumA), j)))
#for g in graph[1:][::-1]:
#   print(*g)

for u, v, a, b in UVAB:
    for i in range(a, sumA + 1):
        if i >= a:
            graph[i][u].append((b, (i - a, v)))
            graph[i][v].append((b, (i - a, u)))
#for g in graph[1:]:
#    print(*g)

#print("")
dist = dijkstra(min(S, sumA), graph)

for j in range(2, N + 1):
    ans = INF
    for i in range(sumA + 1):
        ans = min(dist[i][j], ans)
    print(ans)


# Optimized solution
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
from heapq import heappush, heappop

INF = 10 ** 18

N, M, S = list(map(int, input().split()))
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

sumA = 0
for u, v, a, b in UVAB:
    sumA += a

def dijkstra(start, graph) -> list:
    dist = [[INF for _ in range(N + 1)] for _ in range(sumA + 1)]
    dist[start][1] = 0
    heap = []
    heappush(heap, (0, (start, 1)))
    while heap:
        v, (i, j) = heappop(heap)
        for w, (ni, nj) in graph[i][j]:
            if dist[ni][nj] > v + w:
                dist[ni][nj] = v + w
                heappush(heap, (dist[ni][nj], (ni, nj)))
    return dist

graph = [[[] for _ in range(N + 1)] for _ in range(sumA + 1)]

for u, v, a, b in UVAB:
    for i in range(a, sumA + 1):
        graph[i][u].append((b, (i - a, v)))
        graph[i][v].append((b, (i - a, u)))

for j in range(1, N + 1):
    c, d = CD[j - 1]
    for i in range(sumA):
        graph[i][j].append((d, (min(i + c, sumA), j)))

dist = dijkstra(min(S, sumA), graph)

for j in range(2, N + 1):
    answer = INF
    for i in range(sumA + 1):
        answer = min(dist[i][j], answer)
    print(answer)
# Original solution
import heapq

city_num, road_num, init_silver = map(int, input().split())
init_silver  = min(2500, init_silver)

G = [[] for _ in range(city_num)]
for _ in range(road_num):
    A, B, cost, time_cost = map(int, input().split())
    A, B = A-1, B-1
    G[B].append([A, cost, time_cost])
    G[A].append([B, cost, time_cost])

for n in range(city_num):
    cost, time_cost = map(int, input().split())
    G[n].append([n, -cost, time_cost])

dp = [[float("inf")] * 2501 for _ in range(city_num)]
dp[0][init_silver] = 0
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)
    for to, silver_cost, time_cost in G[node]:
        remain = min(silver - silver_cost, 2500)
        if remain < 0:
            continue
        dp_next_value = time + time_cost
        if dp[to][remain] <= dp_next_value:
            continue
        dp[to][remain] = dp_next_value
        hq.append([dp_next_value, to, remain])
print(*[min(d) for d in dp[1:]], sep="\n")


# Optimized solution
import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    G[i].append([i, -rate, cost])  # これを追加！
    change_rate.append(rate)
    change_cost.append(cost)


# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")
# Original solution
import heapq


def inpl():
    return list(map(int, input().split()))


N, M, S = inpl()
A = 101  # max A
S = min(S, M * A - 1)

lines = [[] for _ in range(N * (M * A))]
for _ in range(M):
    in_s, in_t, cost, time = inpl()
    in_s -= 1
    in_t -= 1

    for n in range(cost, M * A):
        s = in_s + n * N
        t = in_t + (n - cost) * N
        lines[s].append((t, time))

        s = in_s + (n - cost) * N
        t = in_t + n * N
        lines[t].append((s, time))


for i in range(N):
    cost, time = inpl()
    for n in range(0, M * A):
        s = i + n * N
        if n + cost >= M * A:
            t = i + (M * A - 1) * N
        else:
            t = i + (n + cost) * N
        lines[s].append((t, time))


INF = 10**20


def dijkstra(N, S):
    weight = [INF] * N
    weight[S] = 0
    q = [[0, S]]
    heapq.heapify(q)
    while q:
        w0, s = heapq.heappop(q)
        for t, w in lines[s]:
            w += w0
            if weight[t] > w:
                heapq.heappush(q, [w, t])
                weight[t] = w

    return weight


weight = dijkstra(N * (M * A), 0 + S * N)

for i in range(1, N):
    ans = INF
    for n in range(M * A):
        ans = min(ans, weight[i + n * N])
    print(ans)


# Optimized solution
import heapq


def inpl():
    return list(map(int, input().split()))


N, M, S = inpl()
A = 51  # max A
S = min(S, M * A - 1)

lines = [[] for _ in range(N * (M * A))]
for _ in range(M):
    in_s, in_t, cost, time = inpl()
    in_s -= 1
    in_t -= 1

    for n in range(cost, M * A):
        s = in_s + n * N
        t = in_t + (n - cost) * N
        lines[s].append((t, time))

        s = in_s + (n - cost) * N
        t = in_t + n * N
        lines[t].append((s, time))


for i in range(N):
    cost, time = inpl()
    for n in range(0, M * A):
        s = i + n * N
        if n + cost >= M * A:
            t = i + (M * A - 1) * N
        else:
            t = i + (n + cost) * N
        lines[s].append((t, time))


INF = 10**20


def dijkstra(N, S):
    weight = [INF] * N
    weight[S] = 0
    q = [[0, S]]
    heapq.heapify(q)
    while q:
        w0, s = heapq.heappop(q)
        for t, w in lines[s]:
            w += w0
            if weight[t] > w:
                heapq.heappush(q, [w, t])
                weight[t] = w

    return weight


weight = dijkstra(N * (M * A), 0 + S * N)

for i in range(1, N):
    ans = INF
    for n in range(M * A):
        ans = min(ans, weight[i + n * N])
    print(ans)
# Original solution
import heapq


def inpl():
    return list(map(int, input().split()))


N, M, S = inpl()
A = 51  # max A
S = min(S, M * A - 1)

lines = [[] for _ in range(N * (M * A))]
for _ in range(M):
    in_s, in_t, cost, time = inpl()
    in_s -= 1
    in_t -= 1

    for n in range(cost, M * A):
        s = in_s + n * N
        t = in_t + (n - cost) * N
        lines[s].append((t, time))

        s = in_s + (n - cost) * N
        t = in_t + n * N
        lines[t].append((s, time))


for i in range(N):
    cost, time = inpl()
    for n in range(0, M * A):
        s = i + n * N
        if n + cost >= M * A:
            t = i + (M * A - 1) * N
        else:
            t = i + (n + cost) * N
        lines[s].append((t, time))


INF = 10**20


def dijkstra(N, S):
    weight = [INF] * N
    weight[S] = 0
    q = [[0, S]]
    heapq.heapify(q)
    while q:
        w0, s = heapq.heappop(q)
        for t, w in lines[s]:
            w += w0
            if weight[t] > w:
                heapq.heappush(q, [w, t])
                weight[t] = w

    return weight


weight = dijkstra(N * (M * A), 0 + S * N)

for i in range(1, N):
    ans = INF
    for n in range(M * A):
        ans = min(ans, weight[i + n * N])
    print(ans)


# Optimized solution
import heapq

INF = 10**20
A = 50  # max A


def inpl():
    return list(map(int, input().split()))


def main():
    N, M, S = inpl()
    S = min(S, M * A)

    lines = [[] for _ in range(N * (M * A + 1))]
    for _ in range(M):
        in_s, in_t, cost, time = inpl()
        in_s -= 1
        in_t -= 1

        for n in range(cost, M * A + 1):
            s = in_s + n * N
            t = in_t + (n - cost) * N
            lines[s].append((t, time))

            s = in_s + (n - cost) * N
            t = in_t + n * N
            lines[t].append((s, time))

    for i in range(N):
        cost, time = inpl()
        for n in range(0, M * A + 1):
            s = i + n * N
            if n + cost > M * A:
                t = i + (M * A) * N
            else:
                t = i + (n + cost) * N
            lines[s].append((t, time))

    def dijkstra(N, S):
        weight = [INF] * N
        weight[S] = 0
        q = [[0, S]]
        heapq.heapify(q)
        while q:
            w0, s = heapq.heappop(q)
            for t, w in lines[s]:
                w += w0
                if weight[t] > w:
                    heapq.heappush(q, [w, t])
                    weight[t] = w

        return weight

    weight = dijkstra(N * (M * A + 1), 0 + S * N)

    ansl = [INF] * N
    for i, w in enumerate(weight):
        n = i % N
        if n == 0:
            continue
        else:
            ansl[n] = min(w, ansl[n])

    print(("\n".join(map(str, ansl[1:]))))


if __name__ == "__main__":
    main()
# Original solution
import sys
from heapq import heappop, heappush

n, m, ss = list(map(int, input().split()))
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = list(map(int, line.split()))
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = list(map(int, line.split()))
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

print(('\n'.join(map(str, ans[1:]))))


# Optimized solution
import sys
from heapq import heappop, heappush

n, m, ss = list(map(int, input().split()))
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = list(map(int, line.split()))
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = list(map(int, line.split()))
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

print(('\n'.join(map(str, ans[1:]))))
# Original solution
import sys
import heapq

input = sys.stdin.readline

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = list(map(int, input().split()))
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
for i in range(M):
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = list(map(int, input().split()))
    exchanges.append((c, d))


WALLET_MAX = fare_max * (N - 1)
mintime = [[TIME_MAX] * (WALLET_MAX + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, WALLET_MAX))]
    while q:
        t, loc, silvers = heapq.heappop(q)
        if t > mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while True:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], WALLET_MAX)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    mintime[nloc][nsilvers] = ntime
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            if silvers > WALLET_MAX:
                break
            silvers += rate


search()
for t in range(1, N):
    print((min(mintime[t])))


# Optimized solution
import sys
import heapq

input = sys.stdin.readline

NCOSTS = 2501
TIME_MAX = 10 ** 15

N, M, S = list(map(int, input().split()))
adj = [[] for _ in range(N * NCOSTS)]
fare_adj = [[NCOSTS] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0


def node(city, silvers):
    return silvers * N + city


for i in range(M):
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    for j in range(a, NCOSTS):
        adj[node(u, j)].append((node(v, j - a), b))
        adj[node(v, j)].append((node(u, j - a), b))

for i in range(N):
    # g-s rate, waiting duration
    c, d = list(map(int, input().split()))
    for j in range(NCOSTS - c):
        adj[node(i, j)].append((node(i, j + c), d))


mintime = [TIME_MAX for _ in range(N * NCOSTS)]


def search():
    q = [(0, node(0, min(S, NCOSTS - 1)))]
    while q:
        t, node1 = heapq.heappop(q)
        if t > mintime[node1]:
            continue
        for node2, cost in adj[node1]:
            ntime = t + cost
            if mintime[node2] > ntime:
                mintime[node2] = ntime
                heapq.heappush(q, (ntime, node2))


search()
for i in range(1, N):
    print((min(mintime[node(i, j)] for j in range(NCOSTS))))
# Original solution
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**16
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*5005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,5000),0))
    fin=[False]*n
    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        fin[u]=True
        if sum(fin)==n:break
        c,d=cd[u]
        for i in range(1,10000):
            if g+c*i>5000:
                if dp[u][5000] <= t + d * i: continue
                dp[u][5000] = t + d * i
                heappush(hp, (t + d * i, 5000, u))
                break
            if dp[u][g+c*i]<=t+d*i:continue
            dp[u][g + c * i]=t+d*i
            heappush(hp,(t+d*i,g+c*i,u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()


# Optimized solution
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**16
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*3005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,3000),0))
    dp[0][min(s,3000)]=0

    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        c,d=cd[u]
        if g+c<3000:
            if dp[u][g + c] > t + d:
                dp[u][g + c] = t + d
                heappush(hp, (t + d, g + c, u))
        else:
            if dp[u][3000] > t + d:
                dp[u][3000] = t + d
                heappush(hp, (t + d, 3000, u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()