There are N cities numbered 1 to N, connected by M railroads.
You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.
The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes.
You cannot use gold coins to pay the fare.
There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin.
The transaction takes D_i minutes for each gold coin you give.
You can exchange any number of gold coins at each exchange counter.
For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

-----Constraints-----
 - 2 \leq N \leq 50
 - N-1 \leq M \leq 100
 - 0 \leq S \leq 10^9
 - 1 \leq A_i \leq 50
 - 1 \leq B_i,C_i,D_i \leq 10^9
 - 1 \leq U_i < V_i \leq N
 - There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).
 - Each city t=2,...,N can be reached from City 1 with some number of railroads.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N

-----Output-----
For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

-----Sample Input-----
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

-----Sample Output-----
2
14

The railway network in this input is shown in the figure below.
In this figure, each city is labeled as follows:
 - The first line: the ID number i of the city (i for City i)
 - The second line: C_i / D_i
Similarly, each railroad is labeled as follows:
 - The first line: the ID number i of the railroad (i for the i-th railroad in input)
 - The second line: A_i / B_i

You can travel from City 1 to City 2 in 2 minutes, as follows:
 - Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.


You can travel from City 1 to City 3 in 14 minutes, as follows:
 - Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.
 - At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 6 minutes.
 - Use the 1-st railroad to move from City 2 to City 1 in 2 minutes.
 - Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Difficulty: interview

Starter code:

Solutions:
import heapq

city_num, road_num, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver  = min(MAX_COST, 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")] * (MAX_COST+1) 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, MAX_COST)
        if remain < 0:
            continue
        dp_next_value = time + time_cost
        if dp[to][remain] <= dp_next_value:
            continue
        dp[to][remain] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain))
print(*[min(d) for d in dp[1:]], sep="\n")

def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

    es = [[] for _ in range(N)]
    for u,v,a,b in UVAB:
        u,v = u-1,v-1
        es[u].append((v,a,b))
        es[v].append((u,a,b))

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = 0
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached += 1
            if reached == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: break
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()

import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')

import heapq
def dijkstra_heap():
    used = [-1] * (2451*n)
    edgelist=[]
    heapq.heappush(edgelist,[0,ss])
    while 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 = map(int,input().split())
ss=min(2450,ss)
edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = 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)

from heapq import *

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

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

for i in range(M):
  U, V, A, B = tuple(map(int, input().split()))
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

for i in range(1, N):
  print(min(T[i]))

def main():
    import heapq

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

    edges = [[] for _ in range(n)]
    max_cost = 0
    for _ in range(m):
        from_, to, cost, time = map(int, input().split())
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))
        if cost > max_cost:
            max_cost = cost

    banks = []
    for i in range(n):
        coin, time = map(int, input().split())
        banks.append((coin, time))

    max_coin = max_cost * (n-1)
    if s > max_coin:
        s = max_coin

    INF = float('INF')
    DP = [[INF] * (max_coin+1) for _ in range(n)]
    DP[0][s] = 0

    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time

    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin > max_coin:
            new_coin = max_coin
        push_todo(node, new_coin, current_time+time)

    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time > DP[node][current_coin]:
            continue

        charge(node, current_coin, current_time)

        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)

    for node in range(1, n):
        print(min(DP[node]))


def __starting_point():
    main()
__starting_point()

import heapq

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

graph = [[] for _ in range(N)]
for _ in range(M):
	u, v, A, B = list(map(int, input().strip().split()))
	u -= 1
	v -= 1
	graph[u].append((v, A, B))
	graph[v].append((u, A, B))

exchanges = []
for _ in range(N):
	C, D = list(map(int, input().strip().split()))
	exchanges.append((C, D))

queue = [(0, 0, S)]
max_fare = 2500

state_table = [[None] * (max_fare + 1) for i in range(N)]

reached = [False] * N
reached_count = 0

while queue:
#	print(len(queue))
	time, cur, money = heapq.heappop(queue)
	if not reached[cur]:
		reached[cur] = True
		reached_count += 1
		if reached_count >= N:
			break
	count, d_time = exchanges[cur]
	for n, A, B in graph[cur]:
		n_money = money - A
		n_time = time + B
		if n_money >= 0:
			states = state_table[n]
			if n_money > max_fare:
				n_money = max_fare
			if states[n_money] == None or states[n_money] > n_time:
				states[n_money] = n_time
				heapq.heappush(queue, (n_time, n, n_money))

	states = state_table[cur]
	money += count
	time += d_time
	if money >= 0:
		if money > max_fare:
			money = max_fare
		if states[money] == None or states[money] > time:
			states[money] = time
			heapq.heappush(queue, (time, cur, money))

#for i in range(N):
#	print(i, state_table[i])

for i in range(1, N):
	states = state_table[i]
	minimum = None
	for t in states:
		if t != None and (minimum == None or minimum > t):
			minimum = t
	print(minimum)


from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = map(int, input().split())
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    # dijkstra (time, vertex, money)
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        for nv, (a, b) in to[now].items():
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        # exchange gold with silver
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        if cost[now][ns] <= nt : continue
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

def __starting_point():
    main()
__starting_point()

import sys
from heapq import heappush, heappop
import numpy as np

def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():

    def dijkstra(xs, ss):
        def push(v, s, x):
            if s < 0: 
                return
            if dist[v, s] <= x:
                return
            dist[v, s] = x
            heappush(que, (x, v, s))
        
        inf = 10**18
        dist = np.full((n, MAX_S+1), inf, dtype=int)
        # time, remain, node
        que = []
        push(xs, ss, 0)
        while que:
            x, v, s = heappop(que)
            if dist[v, s] < x:
                continue
            ns = min(s+c[v], MAX_S)
            push(v, ns, x+d[v])
            for nv, a, b in adj[v]:
                push(nv, s-a, x+b)
        return np.min(dist, axis=1)

    n, m, s = mi()
    adj = [[] for i in range(n)]
    MAX_S = 0
    for i in range(m):
        u, v, a, b = mi()
        u -= 1
        v -= 1
        adj[u].append((v, a, b))
        adj[v].append((u, a, b))
        MAX_S = max(MAX_S, a)
    MAX_S *= n-1
    s = min(s, MAX_S)
    c, d = [0]*n, [0]*n
    for i in range(n):
        c[i], d[i] = mi()
    ans = dijkstra(0, s)
    print(*ans[1:], sep='\n')


def __starting_point():
    main()
__starting_point()

import sys
import heapq
def input(): return sys.stdin.readline().rstrip()


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

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

maxcoin = 0

for i in range(m):
    u, v, a, b = list(map(int, input().split()))
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))
    maxcoin += a

ryougae = [0, 0]*(n+1)

for i in range(1, n+1):
    c, d = list(map(int, input().split()))
    ryougae[i] = [c, d]


mindist = [[10**20]*(maxcoin+1) for _ in range(n+1)]
hq = []
heapq.heappush(hq, (0, 1, min(maxcoin, s)))
while hq:
    minute, city, coin = heapq.heappop(hq)
    if mindist[city][coin] != 10**20:
        continue
    mindist[city][coin] = minute
    for i, pay, length in graph[city]:
        if coin >= pay:
            if mindist[i][coin-pay] != 10**20:
                continue
            heapq.heappush(hq, (minute+length, i, coin-pay))
    if coin < maxcoin:
        kankin = min(maxcoin, ryougae[city][0]+coin)
        if mindist[city][kankin] != 10**20:
            continue
        heapq.heappush(hq, (minute+ryougae[city][1], city, kankin))

for i in range(2, n+1):
    print((min(mindist[i])))


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)

    # self_loop_silver = min(silver + change_rate[node], MAX_COST)
    # self_loop_cost = time + change_cost[node]
    # if self_loop_cost < dp[node][self_loop_silver]:
    #     dp[node][self_loop_silver] = self_loop_cost
    #     heapq.heappush(hq, (time + change_cost[node], node, self_loop_silver))

    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")


import sys
import heapq
def dijkstra(s,es):
    INF=sys.maxsize
    cs=[INF]*len(es)
    cs[s],hq=0,[]
    heapq.heapify(hq)
    heapq.heappush(hq,(cs[s],s))
    while hq:
        d,v=heapq.heappop(hq)
        if cs[v]<d:continue
        for t,b in es[v]:
            if cs[t]>cs[v]+b:
                cs[t]=cs[v]+b
                heapq.heappush(hq,(cs[t],t))
    return cs
def nwc(n,c):
    MAX_COINS=2500
    return (MAX_COINS+1)*n+c
def main():
    MAX_COINS=2500
    N,M,S=tuple(map(int,sys.stdin.readline().split()))
    S=S if S<MAX_COINS else MAX_COINS
    es=[[] for _ in range(N*(MAX_COINS+1))]
    for _ in range(M):
        u,v,a,b=tuple(map(int,sys.stdin.readline().split()))
        u,v=u-1,v-1
        for c in range(a,MAX_COINS+1):
            es[nwc(u,c)].append((nwc(v,c-a),b))
            es[nwc(v,c)].append((nwc(u,c-a),b))
    for n in range(N):
        c,d=tuple(map(int,sys.stdin.readline().split()))
        c=c if c<MAX_COINS else MAX_COINS
        for i in range(0,MAX_COINS-c+1):es[nwc(n,i)].append((nwc(n,i+c),d))
    cs=dijkstra(nwc(0,S),es)
    for n in range(1,N):print(min(cs[n*(MAX_COINS+1):(n+1)*(MAX_COINS+1)]))
def __starting_point():main()
__starting_point()

import heapq
def main():
    N, M, S = map(int, input().split())
    money_max = 50*N
    S = min(S, money_max)
    dp = [[float("inf")]*(money_max+1) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G[u].append([v, a, b])
        G[v].append([u, a, b])
    for i in range(N):
        c, d = map(int, input().split())
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0, S])
    while 0 < len(q):
        pre_time, idx, s = heapq.heappop(q)
        if dp[idx][s] < pre_time:
            continue
        ex = min(s + exchange[idx][0], money_max)
        if dp[idx][s] + exchange[idx][1] < dp[idx][ex]:
            dp[idx][ex] = dp[idx][s] + exchange[idx][1]
            heapq.heappush(q, [dp[idx][ex], idx, ex])
        for to, money, time in G[idx]:
            if money <= s:
                if dp[idx][s] + time < dp[to][s-money]:
                    dp[to][s-money] = dp[idx][s] + time
                    heapq.heappush(q, [dp[to][s-money], to, s-money])
    for i in range(1, N):
        print(min(dp[i]))

def __starting_point():
    main()
__starting_point()

import heapq as hq
n,m,s = list(map(int,input().split()))
G = [[] for _ in range(n)]

for i in range(m):
  u,v,A,B = list(map(int,input().split()))
  u -= 1
  v -= 1
  hq.heappush(G[u], (B,A,v))
  hq.heappush(G[v], (B,A,u))
  #G[u].append((B,A,v))
  #G[v].append((B,A,u))

c = [0]*n
d = [0]*n
for i in range(n):
  C,D = list(map(int,input().split()))
  c[i] = C
  d[i] = D

inf = 1<<61
M = 50*51
if s > M:s = M-1
dp = [[inf] * M for _ in range(n)] 
cur = 0
dp[cur][s] = 0
que = [(0,s,0)]
while que:
  cd,cs,cur = hq.heappop(que)
  C = c[cur];D = d[cur]
  if dp[cur][cs] < cd:continue
  if cs+C < M and cd+D < dp[cur][cs+C]:
    dp[cur][cs+C] = cd+D
    hq.heappush(que, (cd+D, cs+C, cur))
  for g in G[cur]:
    B = g[0];A = g[1];to = g[2]
    if cs >= A and B+cd < dp[to][cs-A]:
      dp[to][cs-A] = B+cd
      hq.heappush(que, (B+cd, cs-A, to))

for i in range(1,n):
  print((min(dp[i])))


# -*- coding:utf-8 -*-

def solve():
    import sys
    import heapq

    MAX_S = 50*50
    N, M, S = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, a, b = list(map(int, sys.stdin.readline().split()))
        u, v = u-1, v-1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))

    ryogae = []
    for _ in range(N):
        c, d = list(map(int, sys.stdin.readline().split()))
        ryogae.append((c, d))

    # dp[v][s] := 頂点vに所持金sで訪れるときの最小時間
    dp = [[float("inf") for _ in range(MAX_S+1)] for __ in range(N)]

    # ダイクストラ
    s = min(S, MAX_S)
    que = []
    heapq.heappush(que, (0, 0, s))  # (時刻t, 頂点番号v, 所持金s)
    # heapq.heappush(que, (0, s, 0))  # (頂点番号v, 所持金s, 時刻t)

    while len(que) != 0:
        t, v, s = heapq.heappop(que)
        # v, s, t = heapq.heappop(que)

        # if dp[v][s] != t: continue  # なにこれ？

        # 両替する場合
        c, d = ryogae[v]
        ns = min(s+c, MAX_S)
        if dp[v][ns] > t+d:
            dp[v][ns] = t+d
            heapq.heappush(que, (t+d, v, ns))
            # heapq.heappush(que, (v, ns, t+d))

        # 移動する場合(v -> uに移動)
        for u, a, b in graph[v]:
            if s-a < 0: continue
            if dp[u][s-a] > t+b:
                dp[u][s-a] = t+b
                heapq.heappush(que, (t+b, u, s-a))
                # heapq.heappush(que, (u, s-a, t+b))

    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S+1):
            ans = min(ans, dp[v][s])
        print(ans)


def __starting_point():
    solve()

__starting_point()


from heapq import heappush, heappop
def resolve():
    INF = float('inf')
    maxMoney = 2502

    def Dijkstra(g):
        ans = {}
        # ある頂点にいて、ある銀貨の枚数を持っているときのこれまでにかかった最短時間
        dp = [[INF] * (maxMoney + 1) for _ in range(N)]
        # (time, node, silver)
        hq = []
        heappush(hq, (0, 0, min(S, maxMoney)))
        while hq:
            t, v, s = heappop(hq)
            if t > dp[v][s]:
                continue
            if v not in ans:
                ans[v] = t
                if len(ans) == N:
                    break

            # buy
            if s < maxMoney:
                c, d = CD[v]
                new_s = min(s + c, maxMoney)
                new_t = t + d
                if new_t < dp[v][new_s]:
                    dp[v][new_s] = new_t
                    heappush(hq, (new_t, v, new_s))

            # move
            for nv, cost, time in G[v]:
                # 払えない
                if s < cost:
                    continue
                # 払って移動した場合、最短時間なら更新
                new_s = s - cost
                new_t = t + time
                if new_t < dp[nv][new_s]:
                    dp[nv][new_s] = new_t
                    heappush(hq, (new_t, nv, new_s))
        return ans

    N, M, S = list(map(int, input().split()))
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v, coin, tm = list(map(int, input().split()))
        u, v = u - 1, v - 1
        G[u].append((v, coin, tm))
        G[v].append((u, coin, tm))
    CD = [list(map(int, input().split())) for _ in range(N)]

    ans = Dijkstra(G)
    for i in range(1, N):
        print((ans[i]))


def __starting_point():
    resolve()

__starting_point()

from heapq import heappop,heappush
n,m,s=map(int,input().split())
g=[[]for i in range(n)]
x=0
for i in range(m):
    u,v,a,b=map(int,input().split())
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
    x=max(x,a)
for i in range(n):
    c,d=map(int,input().split())
    g[i].append([i,-c,d])
x*=(n-1)
t=[[2**64 for i in range(x+1)]for i in range(n)]
q=[]
heappush(q,(0,0,s))
while q:
    a,b,c=heappop(q)
    for i,j,h in g[b]:
        if c>=j and a+h<t[i][min(x,c-j)]:
            t[i][min(x,c-j)]=a+h
            heappush(q,(a+h,i,c-j))
for i in range(1,n):
    print(min(t[i]))

def main():
    import heapq

    n, m, s = list(map(int, input().split()))
    if s >= 2500:
        s = 2499

    edges = [[] for _ in range(n)]
    for _ in range(m):
        from_, to, cost, time = list(map(int, input().split()))
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))

    banks = []
    for i in range(n):
        coin, time = list(map(int, input().split()))
        banks.append((coin, time))

    INF = float('INF')
    DP = [[INF] * 2500 for _ in range(n)]
    DP[0][s] = 0
    ans = [INF] * n

    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time

    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin >= 2500:
            new_coin = 2499
        push_todo(node, new_coin, current_time+time)

    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time > DP[node][current_coin]:
            continue

        if current_time < ans[node]:
            ans[node] = current_time

        charge(node, current_coin, current_time)

        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)

    for a in ans[1:]:
        print(a)


def __starting_point():
    main()

__starting_point()

def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500

    N, M, S = list(map(int, input().split()))
    S = min(S, MX_AG)  # それ以上のAgは不要

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))

    exchange = []
    for _ in range(N):
        c, d = list(map(int, input().split()))
        exchange.append((c, d))

    h = [(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    # time[location][r_Ag]:=minimum_time_to_reach

    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            n_Ag = ag - fare
            if n_Ag < 0: continue
            cf = time[to][n_Ag]
            n_time = t + dt
            if cf <= n_time: continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))

        e_time = t + exchange[loc][1]
        e_Ag = ag + exchange[loc][0]
        if e_Ag > MX_AG: continue
        cf = time[loc][e_Ag]
        if cf <= e_time: continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))

    for to in range(1, N):
        print((min(time[to])))


def __starting_point():
    main()

__starting_point()

import heapq

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

uvab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(N)]

for i in range(M):
    uvab[i][0] -= 1
    uvab[i][1] -= 1

railways = [[] for _ in range(N)]
max_a = 0
for u, v, a, b in uvab:
    railways[u].append((v, a, b))
    railways[v].append((u, a, b))
    max_a = max(max_a, a)
del uvab

max_silver = max_a * (N - 1)

ans = [-1] * N
d = dict()
d[(S, 0)] = 0  # silver, station
Q = [(0, S, 0)]  # time, silver, station
sum_reached = 0
reached = [False] * N

while Q:
    t, sv, st = heapq.heappop(Q)
    if not reached[st]:
        ans[st] = t
        reached[st] = True
        sum_reached += 1
        if sum_reached == N:
            break

    new_key = (min(max_silver, sv + cd[st][0]), st)
    new_value = t + cd[st][1]
    if new_key not in d or d[new_key] > new_value:
        d[new_key] = t + cd[st][1]
        heapq.heappush(Q, (new_value, *new_key))

    for dist, a, b in railways[st]:
        if sv >= a:
            new_key = (sv - a, dist)
            new_value = t + b
            if new_key not in d or d[new_key] > new_value:
                d[new_key] = new_value
                heapq.heappush(Q, (new_value, *new_key))

print(*ans[1:], sep="\n")


# snuke解説板
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, n * 50)

edges = [[] for _ in range(n + 1)]
# edge:1-50, max silver=0-2500

for _ in range(m):  # a円, b分
    u, v, a, b = map(int, input().split())
    edges[v].append((u, a, b))
    edges[u].append((v, a, b))

exchange = [(0, 0)] * (n + 1)

for edge_num in range(1, n + 1):  # c円, d分
    c, d = map(int, input().split())
    exchange[edge_num] = (c, d)

start = 1
# dp[i][j], 頂点iにお金jを持って到達する最低時間→時間に関してDAG
dp = [[infi] * (n * 50 + 1) for _ in range(n + 1)]


def dijkstra(edges, start, s, dp):
    dp[start][s] = 0
    edgelist = []
    heappush(edgelist, (0, s, start))  # 時間, お金, 頂点
    while edgelist:
        nowtime, nowmoney, nowedge = heappop(edgelist)
        # 遷移させる条件はedge,moneyの組み合わせに対してその時の最小値が出てきたときのみ→最小値以外は飛ばす。
        if dp[nowedge][nowmoney] != nowtime:
            continue
        # 両替
        deltamoney, deltatime = exchange[nowedge]
        nextmoney = min(nowmoney + deltamoney, n * 50)
        nexttime = nowtime + deltatime
        if dp[nowedge][nextmoney] > nexttime:
            dp[nowedge][nextmoney] = nexttime
            heappush(edgelist, (nexttime, nextmoney, nowedge))
        # 移動
        for v, vmoney, vtime in edges[nowedge]:
            nexttime = nowtime + vtime
            nextmoney = nowmoney - vmoney
            if nextmoney < 0:
                continue
            if dp[v][nextmoney] > nexttime:
                dp[v][nextmoney] = nexttime
                heappush(edgelist, (nexttime, nextmoney, v))
    return dp


time = dijkstra(edges, start, s, dp)

ans = [infi] * (n + 1)
for i in range(1, n + 1):
    for j in range(n * 50 + 1):
        ans[i] = min(ans[i], dp[i][j])

print(*ans[2 : (n + 1)], sep="\n")


# 解説と提出#12551970を参考に作成
# 今いる都市と銀貨の所持数を状態として、
#   ①その都市から移動可能な別の都市に移動する
#   ②金貨を銀貨に交換する
# のどちらかを行い、実施後の(同都市・同所持銀貨枚数での)最小時間を計測していく。
# 最小時間が更新された場合、さらにその状態から①・②を行う。
# これによって全都市・全銀貨所持枚数毎の最小時間を割り出す。
# 都市の銀貨所持枚数毎の最小時間の中での最小時間がその都市へ行くための最小時間になる。
#   ※1: 都市への移動は移動可能な枚数の銀貨を持っている場合のみ可能
#   ※2: 銀貨の最大所持枚数は (N - 1) * max(Ai) とする
#        -> 一番遠い都市に移動する場合にかかりうる最大の銀貨枚数

from heapq import heappop, heappush


def solve():
    n, m, s = list(map(int, input().split()))
    graph = [[] for _ in range(n)]
    # グラフ作製
    for _ in range(m):
        u, v, a, b = list(map(int, input().split()))
        graph[u - 1].append([v - 1, a, b])
        graph[v - 1].append([u - 1, a, b])
    ce = [[int(i) for i in input().split()] for _ in range(n)]
    # 初期値マップ作製
    maxSilver = 50 * 49  # max(a) * (n - 1)
    inf = float('inf')
    ns_map = [[inf] * (maxSilver + 1) for _ in range(n)]
    # スタート時の値設定と探索
    q = [[0, 0, min(maxSilver, s)]]  # 累計時間, 都市, 所持銀貨
    ns_map[0][min(maxSilver, s)] = 0  # スタート地点の時刻は0
    while q:
        ti, ni, si = heappop(q)
        # 移動
        for g in graph[ni]:
            n2, ai, bi = g
            if si >= ai and ns_map[n2][si - ai] > ti + bi:
                ns_map[n2][si - ai] = ti + bi
                # ★heapq で累計時間が少ない情報から先に処理するようにする.
                # これによって処理速度が全然違う
                heappush(q, [ti + bi, n2, si - ai])
        # 換金
        ci, di = ce[ni]
        ti += di
        si = min(si + ci, maxSilver)
        if ns_map[ni][si] > ti:
            ns_map[ni][si] = ti
            heappush(q, [ti, ni, si])
    for i in range(1, n):
        print((min(ns_map[i])))


def __starting_point():
    solve()

__starting_point()

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)]
g=[[] for _ in range(n)]
maxs=0
for u,v,a,b in uvab:
    u,v=u-1,v-1
    g[u].append([v,a,b])
    g[v].append([u,a,b])
    maxs+=a

#「現在いる頂点、現在持っている銀貨枚数」を頂点とし、ダイクストラ法でとく。
from heapq import heappop,heappush
inf=float('inf')
ans=[[inf]*(maxs+1) for _ in range(n)]
s=min(s,maxs)
todo=[[0,0,s]]
ans[0][s]=0
while todo:
    t,v,ss=heappop(todo)
    if ans[v][ss]<t:continue
    for nv,na,nb in g[v]:
        if na>ss:continue
        if ans[nv][ss-na]>t+nb:
            heappush(todo,[t+nb,nv,ss-na])
            ans[nv][ss-na]=t+nb
    c,d=cd[v]
    nss=min(ss+c,maxs)
    if ans[v][nss]>t+d:
        heappush(todo,[t+d,v,nss])
        ans[v][nss]=t+d
for i in range(1,n):
    print((min(ans[i])))



from heapq import heappop,heappush

def main():
    N,M,S=map(int,input().split())
    G=[[] for _ in range(N)]
    for i in range(M):
        U,V,A,B=map(int,input().split())
        G[U-1].append([V-1,A,B])
        G[V-1].append([U-1,A,B])
    C=[]
    D=[]
    for _ in range(N):
        c,d=map(int,input().split())
        C.append(c)
        D.append(d)

    MaxMoney=2500

    dp=[[float('inf') for __ in range(MaxMoney+1)] for _ in range(N)]

    cost=0
    money=min(S,MaxMoney)
    que=[]
    heappush(que,(cost,0,money)) #cost,node,money
    dp[0][money] = 0

    while len(que)>0:
        cost,node,money=heappop(que)

        stop_money=min(money+C[node],MaxMoney)
        stop_cost=cost+D[node]
        if stop_cost<dp[node][stop_money]:
            dp[node][stop_money]=stop_cost
            heappush(que,(stop_cost,node,stop_money))

        for to_node,to_money,to_cost in G[node]:
            money_=min(money-to_money,MaxMoney)
            if money_<0:
                continue
            cost_=cost+to_cost
            if dp[to_node][money_]<=cost_:
                continue

            dp[to_node][money_]=cost_
            heappush(que,(cost_,to_node,money_))

    for i in range(1,N):
        print(min(dp[i]))




def __starting_point():
    main()
__starting_point()

import heapq as hq
N,M,S = list(map(int, input().split()))
#Edge
E = [[] for _ in range(N)]
  
for _ in range(M):
  # U <-> V, A coins, B mins
  u,v,a,b = list(map(int, input().split()))
  # 0-indexed
  E[u-1].append([v-1, a, b])
  E[v-1].append([u-1, a, b])

# City
C = []
for _ in range(N):
  # C coins, D mins
  C.append(list(map(int, input().split())))
  
# dp[p][i] 点Pにたどり着いた時、i円持っている時の最小時間
MAXYEN = 50 * N
dp = [[ 1e18 for i in range(MAXYEN + 5) ] for _ in range(N)]
S = min(MAXYEN, S)
dp[0][S] = 0

# 状態は点とお金と時間. time, pointindex, money
Q = []
hq.heapify(Q)
hq.heappush(Q, [0,0,S])

while len(Q) > 0:
  nowt, nowi, nowm = hq.heappop(Q)
  #print("Pop :", nowt, nowi, nowm)
  # Edgeをわたる。a yen払ってB時間かけて、Vに移動する。
  for e in E[nowi]:
    to_i, costm, costt = e
    #print("Edge:", to_i, costm, costt)
    if nowm - costm < 0:
      # unreachable 
      continue
    if dp[to_i][nowm-costm] > dp[nowi][nowm] + costt:
      dp[to_i][nowm-costm] = dp[nowi][nowm] + costt
      hq.heappush(Q, [dp[nowi][nowm] + costt, to_i, nowm-costm])
      
  # その場でお金を1回買う。移動せず、CYenGetして、D時間かける
  getm, costt = C[nowi]
  targetm = min(MAXYEN, nowm + getm)
  #print("Buy :", getm, targetm, costt)
  if dp[nowi][targetm] > dp[nowi][nowm] + costt:
    dp[nowi][targetm] = dp[nowi][nowm] + costt
    hq.heappush(Q, [dp[nowi][targetm], nowi, targetm])
  
for i in range(1,N):
  print((min(dp[i])))
  


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")

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())
    Us[i] -= 1
    Vs[i] -= 1

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(N):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1

row=[]
col=[]
data=[]

if S > Ns:
    S = Ns

# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            row.append( V[(u,ns_s) ])
            col.append( V[(v,ns_g)] )
            data.append( b )
            # V -> U
            row.append( V[(v,ns_s) ])
            col.append( V[(u,ns_g)] )
            data.append( b )

# -----

for i in range(N):
    c,d = map(int,input().split())
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        row.append( V[(i,ns_s) ])
        col.append( V[(i,ns_g)] )
        data.append( d )

graph=coo_matrix((data, (row, col)), shape=(Nv,Nv))

s=V[(0,S)]
dist_matrix = dijkstra(csgraph=graph, directed=True, indices = s)

for i in range(1,N):
    ans = min([dist_matrix[i*(Ns+1)+v] for v in range(Ns+1)])
    print(int(ans))

from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

# グラフを拡張してダイクストラ法を使う

def main():
    N,M,S = list(map(int, readline().split()))

    E = [[] for _ in range(N+1)]
    for _ in range(M):
        u,v,a,b = list(map(int, readline().split()))
        E[u].append((v, a, b))
        E[v].append((u, a, b))

    cd = list(map(int, read().split()))
    CD = []
    for c, d in zip(*[iter(cd)]*2):
        CD.append((c, d))

    # Dijkstra
    # d[v][s] := 頂点vで,所持金sとなる最小の所要時間
    if S > 2500:
        S = 2500 - 1
    INF = 10**15
    d = [[INF] * 2500 for _ in range(N+1)]
    d[1][S] = 0

    Q = []
    heappush(Q, (0, S, 1))  # (所要時間, 所持金, 頂点)
    
    while Q:
        time, s, u = heappop(Q)
        if time > d[u][s]:
            continue
        
        c_u, d_u = CD[u-1]
        if s + c_u < 2500 and time + d_u < d[u][s + c_u]:
            d[u][s + c_u] = time + d_u
            heappush(Q, (time + d_u, s + c_u, u))
        
        for v, a, b in E[u]:
            if s >= a and time + b < d[v][s - a]:
                d[v][s - a] = time + b
                heappush(Q, (time + b, s - a, v))

    for i in range(2,N+1):
        print((min(d[i])))


def __starting_point():
    main()

__starting_point()

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M, S = LI()
    G = [[[] for _ in range(2501)] for _ in range(N)]

    for i in range(M):
        u, v, a, b = LI()
        u -= 1
        v -= 1
        for money in range(2501):
            if money - a < 0 :
                continue
            G[u][money].append((b, v, money - a))
            G[v][money].append((b, u, money - a))

    for i in range(N):
        c, d = LI()
        for money in range(2501):
            new_money = min(2500, money + c)
            G[i][money].append((d, i, new_money))
    def dijkstra(u, s):
        q = []
        d = [[inf for __ in range(2501)] for _ in range(N)]
        visited = set()
        dist = 0
        money = min(2500, s)
        d[u][money] = dist
        heapq.heappush(q, (dist, u, money))
        while len(q) > 0:
            dist, u, u_money = heapq.heappop(q)

            if (u, u_money) in visited:
                continue
            visited.add((u, u_money))
            for next_node_tuple in G[u][u_money]:
                cost, v, v_money = next_node_tuple
                if dist + cost < d[v][v_money]:
                    d[v][v_money] = dist + cost
                    heapq.heappush(q, (d[v][v_money], v, v_money))
        return d
    d = dijkstra(0, S)
    for i in range(1, N):
        print((min(d[i])))

main()



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())
    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)

    self_loop_silver = min(silver + change_rate[node], MAX_COST)
    self_loop_cost = time + change_cost[node]
    if self_loop_cost < dp[node][self_loop_silver]:
        dp[node][self_loop_silver] = self_loop_cost
        heapq.heappush(hq, (time + change_cost[node], node, self_loop_silver))

    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")


import heapq
import sys
input = sys.stdin.readline
 
INF = 10 ** 18
 
class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time
 
dp = []
h = []
 
def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))
 
def dijkstra(n, G, cd, start, s, max_s):
    nonlocal dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)
 
    while h:
        # 使っていない頂点のうち、現時点で最も到達短時間が短いものを選びvとする
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        # 両替
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))
        # vから到達可能な頂点について、到達時間が短くなれば更新
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)
 
 
n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]
 
es = [[] for i in range(n)]
max_s = 50 * (n-1)
 
for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))
 
dijkstra(n, es, cd, 0, min(max_s,s), max_s)
 
for i in range(1, n):
    print(min(dp[i]))

from heapq import *
N, M, S = map(int, input().split())
graph = [[] for _ in range(N)]
amax = 0
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1
  v -= 1
  graph[u].append([v, a, b])
  graph[v].append([u, a, b])
  amax = max(amax, a)
  
lcoins = amax * (N-1)
  
cost = list()
time = list()
for _ in range(N):
  c, d = map(int, input().split())
  cost.append(c)
  time.append(d)

INF = float('INF')
M = 2500
if(S >= M):
  S = M-1

dist = [[INF] * M for _ in range(N)]
dist[0][S] = 0
q = [(0, S, 0)]

while q:
  dv, num, v = heappop(q)
  
  if dist[v][num] < dv:
    continue
    
  if num + cost[v] < M and dv + time[v] < dist[v][num+cost[v]]:
    dist[v][num+cost[v]] = dv + time[v]
    heappush(q, (dv+time[v], num+cost[v], v))
    
  for next, a, b in graph[v]:
    if num >= a and dv+b < dist[next][num-a]:
      dist[next][num-a] = dv+b
      heappush(q, (dv+b, num-a, next))
      
for i in range(1,N):
  print(min(dist[i]))

import heapq


n, m, s = map(int, input().split())
if s >= 2500:
    s = 2499

edges = [[] for _ in range(n)]
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges[from_-1].append((to-1, cost, time))
    edges[to-1].append((from_-1, cost, time))

banks = []
for i in range(n):
    coin, time = map(int, input().split())
    banks.append((coin, time))

INF = float('INF')
DP = [[INF] * 2500 for _ in range(n)]
ans = [INF] * n


def push_todo(node, coin, time):
    if coin < 0:
        return
    if time >= DP[node][coin]:
        return
    heapq.heappush(todo, (time, node, coin))


def charge(node, current_coin, current_time):
    coin, time = banks[node]
    new_coin = current_coin + coin
    if new_coin >= 2500:
        new_coin = 2499
    push_todo(node, new_coin, current_time+time)


todo = [(0, 0, s)]
while todo:
    current_time, node, current_coin = heapq.heappop(todo)
    if current_time >= DP[node][current_coin]:
        continue

    if current_time < ans[node]:
        ans[node] = current_time

    DP[node][current_coin] = current_time
    charge(node, current_coin, current_time)

    for to, cost, time in edges[node]:
        push_todo(to, current_coin-cost, current_time+time)

for a in ans[1:]:
    print(a)

from collections import defaultdict
import heapq
N,M,S = list(map(int,input().split()))
E=[list(map(int,input().split())) for _ in range(M)]

C=[list(map(int,input().split())) for _ in range(N)]

A_max=max([a for _,_,a,_ in E])*N

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        from_state_u=(u,from_a)
        to_state_v=(v,from_a-a)
        D[from_state_u].append((b,to_state_v))

        from_state_v=(v,from_a)
        to_state_u=(u,from_a-a)
        D[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(C):
    for a in range(A_max+1):
        a_after=min(A_max,a+c)
        from_state=(n,a)
        to_state=(n,a_after)
        D[from_state].append((d,to_state))


start=(0,min(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)


import math
import heapq

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())
    Us[i] -= 1
    Vs[i] -= 1

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(N):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1

G=[[] for _ in range(Nv)]

if S > Ns:
    S = Ns

# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            G[ V[(u,ns_s)] ].append( (V[(v,ns_g)],b) )
            # V -> U
            G[ V[(v,ns_s)] ].append( (V[(u,ns_g)],b) )
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        G[ V[(i,ns_s)] ].append( (V[(i,ns_g)],d) )

# -----
D=[math.inf]*Nv
q=[]
# -----

s=V[(0,S)]
D[s] = 0
heapq.heappush(q,(0,s))

while len(q) > 0:
    p_cost,p_v = heapq.heappop(q)
    if D[p_v] < p_cost:
        continue
    for e_to,e_cost in G[p_v]:
        if D[ e_to ] > D[p_v] + e_cost:
            D[e_to] = D[p_v] + e_cost
            heapq.heappush(q, (D[e_to], e_to))

for i in range(1,N):
    ans = min([D[i*(Ns+1)+v] for v in range(Ns+1)])
    print(ans)

from heapq import *

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

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

for i in range(M):
  U, V, A, B = list(map(int, input().split()))
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    # 両替の結果2450枚を超えるなら2450枚として扱って問題なし。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

for i in range(1, N):
  print((min(T[i])))


N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

# -*- coding:utf-8 -*-

def solve():
    """解説実装"""
    import sys
    import heapq

    MAX_S = 50*50
    N, M, S = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, a, b = list(map(int, sys.stdin.readline().split()))
        u, v = u-1, v-1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))

    ryogae = []
    for _ in range(N):
        c, d = list(map(int, sys.stdin.readline().split()))
        ryogae.append((c, d))

    # dp[v][s] := 頂点vに所持金sで訪れるときの最小時間
    dp = [[float("inf") for _ in range(MAX_S+1)] for __ in range(N)]

    # ダイクストラ
    s = min(S, MAX_S)
    que = []
    heapq.heappush(que, (0, 0, s))  # (時刻t, 頂点番号v, 所持金s)

    while len(que) != 0:
        t, v, s = heapq.heappop(que)

        # if dp[v][s] != t: continue  # なにこれ？

        # 両替する場合
        c, d = ryogae[v]
        ns = min(s+c, MAX_S)
        if dp[v][ns] > t+d:
            dp[v][ns] = t+d
            heapq.heappush(que, (t+d, v, ns))

        # 移動する場合(v -> uに移動)
        for u, a, b in graph[v]:
            if s-a < 0: continue
            if dp[u][s-a] > t+b:
                dp[u][s-a] = t+b
                heapq.heappush(que, (t+b, u, s-a))

    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S+1):
            ans = min(ans, dp[v][s])
        print(ans)


def __starting_point():
    solve()

__starting_point()

import math

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

road = []
for i in range(m):
    u,v,a,b = map(int,input().split())
    road.append([u,v,a,b])

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

tree = [[] for _ in range(n+1)]

for i in range(m):  
    r = road[i]
    tree[r[0]].append([r[0],r[1],r[2],r[3]])
    tree[r[1]].append([r[1],r[0],r[2],r[3]])

least_cost = [[] for _ in range(n+1)]
for l in range(n+1):
    least_cost[l] = [math.inf]*2501


def insort_queue(q,v):
    len_a = len(q)    
    if len_a == 0:
        q.append(v)
        return
    
    min = 0
    max_1 = len_a

    if max_1 == 1:
        if v[2] > q[0][2]:
            min = 1
        else:
            min = 0
    while max_1 - min > 1:
        mid = (max_1 + min) //2
        if v[2] > q[mid][2]:
            min = mid
        else:
            max_1 = mid
    index = max_1
    q.insert(index,v)

queue = []

#hwd [location, money, time]
def dijakstra(q):
    while q != []:
        hwd = q.pop(0)

        if least_cost[hwd[0]][hwd[1]] > hwd[2]:
            least_cost[hwd[0]][hwd[1]] = hwd[2]
            
            for node in tree[hwd[0]]:
                # from node, to node , money, time
                if hwd[1] - node[2] >= 0:
                    insort_queue(q,[node[1],hwd[1]-node[2],hwd[2]+node[3]])
            if hwd[1] + change[hwd[0]-1][0] <= 500:
                insort_queue(q,[hwd[0],hwd[1]+change[hwd[0]-1][0],hwd[2]+change[hwd[0]-1][1]])
    return least_cost

if s > 2500:
    s = 2500
queue.append([1,s,0])

ans = dijakstra(queue)

for i in range(2,n+1):
    print(min(ans[i]))

import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline


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

row = []    #start
col = []    #end
data = []

for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for i in range(a, 2501):
        row.append(N * i + u)
        col.append(N * (i - a) + v)
        data.append(b)
        row.append(N * i + v)
        col.append(N * (i - a) + u)
        data.append(b)

for u in range(N):
    c, d = map(int, input().split())
    for i in range(1, c):
        row.append(N * (2500 - i) + u)
        col.append(N * 2500 + u)
        data.append(d)
    for i in range(c, 2501):
        row.append(N * (i - c) + u)
        col.append(N * i + u)
        data.append(d)

graph = csr_matrix((data, (row, col)), shape = (2501*N, 2501*N))

times = dijkstra(graph, directed  = True, indices = N * S)

for end in range(1, N):
    print(int(min(times[N * i + end] for i in range(2501))))

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")

# セイウチ

def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500

    N, M, S = map(int, input().split())
    S = min(S, MX_AG)  # それ以上のAgは不要

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))

    exchange = []
    for _ in range(N):
        c, d = map(int, input().split())
        exchange.append((c, d))

    h = [(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    # time[location][r_Ag]:=minimum_time_to_reach

    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            if (n_Ag := ag - fare) < 0: continue
            if time[to][n_Ag] <= (n_time := t + dt): continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))

        if (e_Ag := ag + exchange[loc][0]) > MX_AG: continue
        if time[loc][e_Ag] <= (e_time := t + exchange[loc][1]): continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))

    ans = (min(time[to]) for to in range(1, N))

    print(*ans, sep='\n')


def __starting_point():
    main()

__starting_point()

N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = 10**18
cost=[[] for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
def __starting_point():
  main()

__starting_point()

import heapq
import sys
input = sys.stdin.readline

INF = 10 ** 18

class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time

dp = []
h = []

def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))

def dijkstra(n, G, cd, start, s, max_s):
    nonlocal dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)

    while h:
        # 使っていない頂点のうち、現時点で最も到達短時間が短いものを選びvとする
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        # 両替
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))
        # vから到達可能な頂点について、到達時間が短くなれば更新
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)


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)]

es = [[] for i in range(n)]
max_s = 50 * (n-1)

for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))

dijkstra(n, es, cd, 0, min(max_s,s), max_s)

for i in range(1, n):
    print((min(dp[i])))




n, m, s = map(int, input().split())
rail = [[] for _ in range(n)]
fare = [[] for _ in range(n)]
time = [[] for _ in range(n)]
rate = []
TIME = []
for _ in range(m):
    i, j, k, l = map(int, input().split())
    i -= 1
    j -= 1
    rail[i].append(j)
    rail[j].append(i)
    fare[i].append(k)
    fare[j].append(k)
    time[i].append(l)
    time[j].append(l)
for _ in range(n):
    i, j = map(int, input().split())
    rate.append(i)
    TIME.append(j)
    
# Dijkstra's algorithm
# 銀貨の枚数がlimit以上になったら捨てる
limit = [max(i) for i in fare]
limit = max(limit) * n
if s >= limit:
    s = limit - 1

# dp[i][j] = 都市iで銀貨j枚を持っているための必要最小時間
dp = [[float('inf')] * limit for _ in range(n)]

# candidateに(必要時間, 都市番号, 銀貨の枚数)を追加していく
import heapq
candidate = [(0, 0, s)]
heapq.heapify(candidate)

ans = [-1] * n
todo = n

while todo > 0:
    i, j, k = heapq.heappop(candidate)
    if dp[j][k] != float('inf'):
        continue
    dp[j][k] = i
    if ans[j] == -1:
        ans[j] = i
        todo -= 1

    # 鉄道移動をcandidateに追加
    for l in range(len(rail[j])):
        if fare[j][l] <= k and dp[rail[j][l]][k - fare[j][l]] == float('inf'):
            heapq.heappush(candidate, (i + time[j][l], rail[j][l], k - fare[j][l]))
    
    # 両替をcandidateに追加
    if k < limit - 1:
        heapq.heappush(candidate, (i + TIME[j], j, min([k + rate[j], limit - 1])))

for i in range(1, n):
    print(ans[i])

import heapq


n, m, s = list(map(int, input().split()))
if s >= 2500:
    s = 2499

edges = [[] for _ in range(n)]
for _ in range(m):
    from_, to, cost, time = list(map(int, input().split()))
    edges[from_-1].append((to-1, cost, time))
    edges[to-1].append((from_-1, cost, time))

banks = [(0, 0) for _ in range(n)]
for i in range(n):
    coin, time = list(map(int, input().split()))
    banks[i] = (coin, time)

INF = float('INF')
DP = [INF] * (n * 2500)
ans = [INF] * n


def to_one_dimension(node, coin):
    return node * 2500 + coin


def push_todo(node, coin, time):
    if coin < 0:
        return
    if time >= DP[to_one_dimension(node, coin)]:
        return
    heapq.heappush(todo, (time, node, coin))


def charge(node, current_coin, current_time):
    coin, time = banks[node]
    new_coin = current_coin + coin
    if new_coin >= 2500:
        new_coin = 2499
    push_todo(node, new_coin, current_time+time)


todo = [(0, 0, s)]
while todo:
    current_time, node, current_coin = heapq.heappop(todo)
    if current_time < ans[node]:
        ans[node] = current_time

    one_d_idx = to_one_dimension(node, current_coin)
    if current_time >= DP[one_d_idx]:
        continue

    DP[one_d_idx] = current_time
    charge(node, current_coin, current_time)

    for to, cost, time in edges[node]:
        push_todo(to, current_coin-cost, current_time+time)

for a in ans[1:]:
    print(a)


import sys
# sys.setrecursionlimit(10**7)  # ネスト回数制限（いる？）

# 入力値を扱いやすい形で格納していく

# input=sys.stdin.buffer.readline  # input の高速化（今回は外す）

N, M, S = map(int,input().split())  # 頂点数／辺数／初期所持金(state)
S=min(S,2500)  # 高々 2500 あれば良い（全都市を回るのに払いきれる回数）

INF=10**18
dp = [[INF]*2501 for _ in range(N)]
way=[[]for _ in range(N)]

for _ in range(M):
    u,v,a,b=map(int,input().split())
    way[u-1].append((v-1,a,b))
    way[v-1].append((u-1,a,b))

# 両替比率と時間
# CD = [list(map(int,input().split())) for _ in range(N)]  # list化する意味は？
CD = [tuple(map(int,input().split())) for _ in range(N)]

from heapq import heappush,heappop

# q は 時間／都市名／所持金　の順番 <- 時間をキーに heapq を使うため

q=[(0,0,S)]  # スタート状態

while q:
    t, u, s = heappop(q)  # 最も到着時間の短い都市 u を選択
    for nxt, a, b in way[u]:  # u からたどり着ける都市 nxt に対して
        if s >= a:  # 交通費がある場合

            if dp[nxt][s-a] > t + b:  # 到着時間を検討
                dp[nxt][s-a] = t + b  # 早いので書き換え
                heappush(q,(t + b, nxt, s-a))  #  キューに次の都市候補として登録しておく
                # 同じ都市 & 同じ金額 が複数個登録されないか？ 計算回数は
                # 更新された = 周囲の都市（点）にたどり着く値を更新する必要があるかもしれないから
                # 検討対象になる

        # この時点では、u にいて、所持金 s でたどり着けないとしてはまだ更新されていない
                
    c, d = CD[u]
    nc = min(2500, c + s)  # 所持金を増やす
    nt= t + d  # 時間も掛かる

    if nt < dp[u][nc]:  # 交換後の金額と時間を見て、更新する（無限大だけが更新になる？）
        dp[u][nc] = nt
        heappush(q, (nt, u, nc))  # 同じ都市（点）だが、違う状態が登録されている

for i in range(1,N):
    print(min(dp[i]))

#拡張ダイクストラ 
#weight,point
N,M,S=map(int,input().split())
graph={(i,j):[] for i in range(1,51) for j in range(2501)}
for _ in range(M):
    u,v,a,b=map(int,input().split())
    for i in range(a,2501):
        graph[(u,i)].append((b,(v,i-a)))
        graph[(v,i)].append((b,(u,i-a)))
for i in range(N):
    c,d=map(int,input().split())
    for j in range(2501):
        graph[(i+1,j)].append((d,(i+1,min(2500,j+c))))

dist={(i,j):float("inf")  for i in range(1,51) for j in range(2501)}

dist[(1,min(2500,S))]=0
pq=[]
import heapq
heapq.heapify(pq)
heapq.heappush(pq,(0,(1,min(2500,S))))
while pq:
    mini_dis,node=heapq.heappop(pq)
    if dist[node]<mini_dis: continue
    for w,point in graph[node]:
        if dist[point]<w:continue
        newlen=dist[node]+w
        if newlen<dist[point]:
            heapq.heappush(pq,(newlen,point))
            dist[point]=newlen
for i in range(2,N+1):
    ans=10**20
    for j in range(2501):
        ans=min(ans,dist[(i,j)])
    print(ans)

def main():
    import dataclasses
    from heapq import heappush, heappop

    @dataclasses.dataclass(frozen=True)
    class Path:
        to: int
        fare: int
        travel_time: int

    @dataclasses.dataclass(frozen=True)
    class ExchangeRate:
        Ag: int
        exchange_time: int

    @dataclasses.dataclass(frozen=True)
    class Traveler:
        consumption_time: int
        remaining_Ag: int
        location: int

        def __gt__(self, other):
            return self.consumption_time > other.consumption_time

        def __eq__(self, other):
            return self.consumption_time == other.consumption_time

    INF = 1 << 60
    MX_AG = 2500

    N, M, S = list(map(int, input().split()))
    S = min(S, MX_AG)  # それ以上のAgは不要

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        g[u].add(Path(v, a, b))
        g[v].add(Path(u, a, b))

    exchange = []
    for _ in range(N):
        c, d = list(map(int, input().split()))
        exchange.append(ExchangeRate(c, d))

    h = [Traveler(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    # time[location][r_Ag]:=minimum_time_to_reach

    while h:
        t = heappop(h)
        for p in g[t.location]:
            n_Ag = t.remaining_Ag - p.fare
            if n_Ag < 0: continue
            cf = time[p.to][n_Ag]
            n_time = t.consumption_time + p.travel_time
            if cf <= n_time: continue
            time[p.to][n_Ag] = n_time
            heappush(h, Traveler(consumption_time=n_time, remaining_Ag=n_Ag, location=p.to))

        e_time = t.consumption_time + exchange[t.location].exchange_time
        e_Ag = t.remaining_Ag + exchange[t.location].Ag
        if e_Ag > MX_AG: continue
        cf = time[t.location][e_Ag]
        if cf <= e_time: continue
        time[t.location][e_Ag] = e_time
        heappush(h, Traveler(consumption_time=e_time, remaining_Ag=e_Ag, location=t.location))

    for to in range(1, N):
        print((min(time[to])))


def __starting_point():
    main()

__starting_point()

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 銀貨を何枚持っているかの状態数、N*2501の都市, dijkstra
N, M, S = lr()
limit = 2500
S = min(S, limit)
graph = [[] for _ in range((N+1) * (limit+1))]  # 1-indexed
for _ in range(M):
    u, v, a, b = lr()
    for x in range(a, limit+1):
        graph[u*(limit+1) + x].append(((v*(limit+1)+x-a), b))
        graph[v*(limit+1) + x].append(((u*(limit+1)+x-a), b))

for i in range(N):
    i += 1
    c, d = lr()
    for x in range(limit-c+1):
        graph[i*(limit+1) + x].append((i*(limit+1) + x + c, d))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * ((N+1) * (limit+1))
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, time in graph[prev]:
            d1 = d + time
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist = dijkstra(1*(limit+1)+S)
for i in range(2, N+1):
    answer = min(dist[i*(limit+1):(i+1)*(limit+1)])
    print(answer)


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

# 所持銀が2500超えたら、2500になるまで銀貨捨てる
# 2500枚以上のDP表を作ると、かなりのメモリ消費するし、このケースでは2500枚あればどこでも行けるので意味ない
s=min(s,2500)

# 2501×nの[]行列
# 0~2500枚 × 頂点数
edge=[[[] for i in range(50*50+1)] for i in range(n)]

# (頂点, コスト)→(頂点, コスト)へ辺を渡っての遷移（頂点が変わる）
# u,v,a,bが与えられるたびに、edgeを更新
for i in range(m):
    u,v,a,b=list(map(int,input().split()))
    
    # jは、保有銀貨枚数
    # j:a→2500なのは、jがa未満であれば、隣の頂点に行けないから
    for j in range(a,2501):
        edge[u-1][j].append((v-1,j-a,b))
        edge[v-1][j].append((u-1,j-a,b))
        
# (頂点, コスト)→(頂点, コスト)へ、その頂点に留まって両替の遷移（頂点変わらない）
# c,dが与えられるたびに、edgeを更新
for i in range(n):
    c,d=list(map(int,input().split()))
      
    # 銀貨を捨てるのはノーコスト
    # 2500枚以上持ってたら、2500枚持ってることと同値と考える
    # range(2501)にしない理由は、2500枚あったら、両替はしないから
    for j in range(2500):
        if j+c>=2500:
            edge[i][j].append((i,2500,d))
        elif j+c<2500:
            edge[i][j].append((i,j+c,d))
        
from heapq import heappush,heappop,heapify

# dはn×2501のすべての状態の最小コストの表
d=[[float('inf')  for i in range(50*50+1)] for i in range(n)]

# 初期値。頂点0, 銀貨Sには、コスト0で到達
d[0][s]=0

pq = []
heappush(pq,(0,0,s))

while len(pq):
    # [コスト, 頂点, 銀貨数]で、コストをkeyとして、heapソートして、一番コストが低いリストを先頭に持ってくる
    _,u,g = heappop(pq)
    
    # 頂点までのコストが更新できれば更新してヒープに登録
    # edge[u][g]は、頂点u, 銀貨g枚の状態から、行ける状態のtuple(頂点, 銀貨数, コスト)を呼び出す
    # pqには、[コスト, 頂点, 銀貨数]の順で入れている
    for tuple in edge[u][g]:
        if d[tuple[0]][tuple[1]]>d[u][g]+tuple[2]:
            d[tuple[0]][tuple[1]]=d[u][g]+tuple[2]
            heappush(pq,[d[u][g]+tuple[2],tuple[0],tuple[1]])
        
# d[i]で、頂点iにおける保有銀貨数に応じたコストが入ったリストを呼び出せる
# リストの中で、一番小さいコストのやつを呼び出せば、その頂点に行ける最小コストと同値である
for i in range(1,n):
    print((min(d[i])))


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)


import heapq

n,m,s=list(map(int,input().split()))
limit=2500
s=min(s,limit)
path=[[] for _ in range(n+1)]
coin=[(0,0)]
time=[[float("inf") for _ in range(limit+1)] for _ in range(n+1)]
queue=[]

for i in range(m):
    u,v,a,b=list(map(int,input().split()))
    path[u].append((v,a,b))
    path[v].append((u,a,b))

for i in range(n):
    c,d=list(map(int,input().split()))
    coin.append((c,d))

time[1][s]=0
heapq.heappush(queue,(0,1,s))

while len(queue)!=0:
    t,v,c=heapq.heappop(queue)
    for nv,na,nb in path[v]:
        if na>c:
            continue
        elif time[nv][c-na]<=t+nb:
            continue
        else:
            time[nv][c-na]=t+nb
            heapq.heappush(queue,(t+nb,nv,c-na))

    nc=min(c+coin[v][0],limit)
    nt=t+coin[v][1]
    if time[v][nc]<=nt:
        continue
    else:
        time[v][nc]=nt
        heapq.heappush(queue,(nt,v,nc))
    
for i in range(2,n+1):
    print((min(time[i])))


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

edges = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = list(map(int, input().split()))
    u, v = u-1, v-1
    edges[u].append((v, a, b))
    edges[v].append((u, a, b))

banks = tuple(tuple(map(int, input().split())) for _ in range(n))

max_s = 50 * (n-1)

s = min(s, max_s)

import heapq

h = []
dp = [[float('inf')] * (max_s+1) for _ in range(n)]
ans = [float('inf')] * n

heapq.heappush(h, (0, 0, s))
while h:
    time, node, coin = heapq.heappop(h)
    if time >= dp[node][coin]:
        continue
    dp[node][coin] = time
    if time < ans[node]:
        ans[node] = time

    c, d = banks[node]
    if coin < max_s:
        heapq.heappush(h, (time+d, node, min(coin + c, max_s)))

    for n, a, b in edges[node]:
        new_time = time + b
        new_coin = coin - a
        if new_coin < 0 or new_time >= dp[n][new_coin]:
            continue
        heapq.heappush(h, (new_time, n, new_coin))

for a in ans[1:]:
    print(a)


import sys
from heapq import *
input = sys.stdin.readline


def main():
    n, m, s = list(map(int, input().split()))
    
    s = min(s, 2500)
    
    railway = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = list(map(int, input().split()))
        railway[u-1].append((v-1, a, b))
        railway[v-1].append((u-1, a, b))
    
    exchange = [None]*n
    for i in range(n):
        exchange[i] = tuple(map(int, input().split()))
    
    
    judge = [(0, 0, s)]
    heapify(judge)
    time = [[-1]*2501 for _ in range(n+1)]*n
    
    while judge:
        t, now, money = heappop(judge)
        if time[now][money] == -1:
            time[now][money] = t
        elif time[now][money] <= t:
            continue
        else:
            time[now][money] = min(time[now][money], t)
        
        if money < 2500:
            c, d = exchange[now]
            if time[now][min(2500, money+c)] == -1:
                heappush(judge, (t+d, now, min(2500, money+c)))
        for (v, a, b) in railway[now]:
            if money-a < 0:
                continue
            if time[v][money-a] == -1:
                heappush(judge, (t+b, v, money-a))
    
    for i in range(1, n):
        print((min(time[i])))
    
    
def __starting_point():
    main()

__starting_point()

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

# 2501×nの[]行列
# 0~2500枚 × 頂点数
edge=[[[] for i in range(50*50+1)] for i in range(n)]

# (頂点, コスト)→(頂点, コスト)へ辺を渡っての遷移（頂点が変わる）
# u,v,a,bが与えられるたびに、edgeを更新
for i in range(m):
    u,v,a,b=list(map(int,input().split()))
    
    # jは、保有銀貨枚数
    # j:a→2500なのは、jがa未満であれば、隣の頂点に行けないから
    for j in range(a,2501):
        edge[u-1][j].append((v-1,j-a,b))
        edge[v-1][j].append((u-1,j-a,b))

# (頂点, コスト)→(頂点, コスト)へ、その頂点に留まって両替の遷移（頂点変わらない）
# c,dが与えられるたびに、edgeを更新
for i in range(n):
    c,d=list(map(int,input().split()))
      
    # 銀貨を捨てるのはノーコスト
    # 2500枚以上持ってたら、2500枚持ってることと同値と考える
    for j in range(2500):
        if j+c>=2500:
            edge[i][j].append((i,2500,d))
        elif j+c<2500:
            edge[i][j].append((i,j+c,d))
        
from heapq import heappush,heappop,heapify

# dはn×2501のすべての状態の最小コストの表
d=[[float('inf')  for i in range(50*50+1)] for i in range(n)]

# 初期値。頂点0, 銀貨Sには、コスト0で到達
d[0][s]=0

pq = []
heappush(pq,(0,0,s))

while len(pq):
    # [コスト, 頂点, 銀貨数]で、コストをkeyとして、heapソートして、一番コストが低いリストを先頭に持ってくる
    _,u,g = heappop(pq)
    
    # 頂点までのコストが更新できれば更新してヒープに登録
    # edge[u][g]は、頂点u, 銀貨g枚の状態から、行ける状態のtuple(頂点, 銀貨数, コスト)を呼び出す
    # pqには、[コスト, 頂点, 銀貨数]の順で入れている
    for tuple in edge[u][g]:
        if d[tuple[0]][tuple[1]]>d[u][g]+tuple[2]:
            d[tuple[0]][tuple[1]]=d[u][g]+tuple[2]
            heappush(pq,[d[u][g]+tuple[2],tuple[0],tuple[1]])
            
# d[i]で、頂点iにおける保有銀貨数に応じたコストが入ったリストを呼び出せる
# リストの中で、一番小さいコストのやつを呼び出せば、その頂点に行ける最小コストと同値である
for i in range(1,n):
    print((min(d[i])))


# ダイクストラ
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from heapq import heappush, heappop

    N, M, S = map(int, input().split())
    S = min(S, 2500)
    graph = [[] for _ in range(N)]

    for u, v, a, b in (map(int, input().split()) for _ in range(M)):
        graph[u-1].append((v-1, a, b))
        graph[v-1].append((u-1, a, b))

    for i, (c, d) in enumerate(map(int, input().split()) for _ in range(N)):
        graph[i].append((i, -c, d))

    hq = [(0, 0, S)]
    INF = 10**18
    # dp[v][silver]
    # 都市vにsilverを使って到達したときの時間の最小値
    dp = [[INF]*2501 for _ in range(N)]
    dp[0][S] = 0

    while hq:
        time, v, silver = heappop(hq)
        if dp[v][silver] < time:
            continue

        for dest, a, b in graph[v]:
            next_s = silver-a if silver-a < 2500 else 2500
            if next_s < 0 or dp[dest][next_s] <= time+b:
                continue
            for i in range(next_s, -1, -1):
                if dp[dest][i] > time+b:
                    dp[dest][i] = time+b
                else:
                    break
            heappush(hq, (time+b, dest, next_s))

    print(*(min(dp[i]) for i in range(1, N)), sep='\n')

main()



from heapq import *

n, m, s = map(int, input().split())
s = min([s, 50*n])
tree = [[] for _i in range(n+1)]
for _i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u].append([v, a, b])
    tree[v].append([u, a, b])

cd = [[0,0]]
for _i in range(n):
    cd.append(list(map(int, input().split())))

dp = [[float('inf') for _i in range(50*n+1)] for _j in range(n+1)]
hq = [[0, 1, s]]
dp[1][s] = 0
heapify(hq)
while hq:
    t, p, g = heappop(hq)
    if g+cd[p][0] <= 50*n:
        x, y = t+cd[p][1], min([g+cd[p][0], 50*n])
        if dp[p][y] > x:
            dp[p][y] = x
            heappush(hq, [x, p, y])
    for x, y, z in tree[p]:
        if g-y >= 0 and dp[x][g-y] > t+z:
            dp[x][g-y] = t+z
            heappush(hq, [t+z, x, g-y])

for i in dp[2:]:
    print(min(i))

# 解説と提出#12551970を参考に作成
# 今いる都市と銀貨の所持数を状態として、
#   ①その都市から移動可能な別の都市に移動する
#   ②金貨を銀貨に交換する
# のどちらかを行い、実施後の(同都市・同所持銀貨枚数での)最小時間を計測していく。
# 最小時間が更新された場合、さらにその状態から①・②を行う。
# これによって全都市・全銀貨所持枚数毎の最小時間を割り出す。
# 都市の銀貨所持枚数毎の最小時間の中での最小時間がその都市へ行くための最小時間になる。
#   ※1: 都市への移動は移動可能な枚数の銀貨を持っている場合のみ可能
#   ※2: 銀貨の最大所持枚数は (N - 1) * max(Ai) とする
#        -> 一番遠い都市に移動する場合にかかりうる最大の銀貨枚数

from heapq import heappop, heappush


def solve():
    n, m, s = list(map(int, input().split()))
    graph = [[] for _ in range(n)]
    # グラフ作製
    max_a = 0
    for _ in range(m):
        u, v, a, b = list(map(int, input().split()))
        graph[u - 1].append([v - 1, a, b])
        graph[v - 1].append([u - 1, a, b])
        max_a = max(max_a, a)
    ce = [[int(i) for i in input().split()] for _ in range(n)]
    # 初期値マップ作製
    maxSilver = max_a * (n - 1)  # max(a) * (n - 1)
    inf = float('inf')
    ns_map = [[inf] * (maxSilver + 1) for _ in range(n)]
    # スタート時の値設定と探索
    q = [[0, 0, min(maxSilver, s)]]  # 累計時間, 都市, 所持銀貨
    ns_map[0][min(maxSilver, s)] = 0  # スタート地点の時刻は0
    while q:
        ti, ni, si = heappop(q)
        # 移動
        for g in graph[ni]:
            n2, ai, bi = g
            if si >= ai and ns_map[n2][si - ai] > ti + bi:
                ns_map[n2][si - ai] = ti + bi
                # ★heapq で累計時間が少ない情報から先に処理するようにする.
                # これによって処理速度が全然違う
                heappush(q, [ti + bi, n2, si - ai])
        # 換金
        ci, di = ce[ni]
        ti += di
        si = min(si + ci, maxSilver)
        if ns_map[ni][si] > ti:
            ns_map[ni][si] = ti
            heappush(q, [ti, ni, si])
    for i in range(1, n):
        print((min(ns_map[i])))


def __starting_point():
    solve()

__starting_point()

from heapq import heapify,heappush,heappop

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

# !!グラフの作成!! #
tmp = [list(map(int, input().split())) for _ in range(M)]

U = [0 for _ in range(M)]
V = [0 for _ in range(M)]
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]

for i in range(M):
  U[i] = tmp[i][0] -1
  V[i] = tmp[i][1] -1
  A[i] = tmp[i][2]
  B[i] = tmp[i][3]
A_m = max(A)
S = min(N*A_m, S)
#print(A_m)

I = [[] for _ in range(N * (N*A_m+1))] 
# 隣接リスト(頂点iで銀貨j枚持ちのとき、i*N*(A_m+1)+jとおく)
for i in range(M):
  for j in range(A[i], N*A_m+1):
    I[U[i]*(N*A_m+1)+j].append((V[i]*(N*A_m+1)+j-A[i],B[i]))
    I[V[i]*(N*A_m+1)+j].append((U[i]*(N*A_m+1)+j-A[i],B[i]))

for i in range(N):
  C, D = map(int, input().split())
  for j in range(N*A_m+1):
    I[i*(N*A_m+1)+j].append((i*(N*A_m+1)+min(C+j,N*A_m),D))
#print(I)

def dijkstra(I):# I:隣接リスト(頂点、コスト、そのほか制約) 
  N = len(I)
  task = [] 
  visited = [0 for _ in range(N)]
  min_cost = [0 for _ in range(N)]
  cost = [10**20 for _ in range(N)]
  prev_points = [0 for _ in range(N)]
  heappush(task, (0, S, -1))
  # !!比較値がスカラーでないときは、一番左の0を適宜変更する!! #
  # !!最初の点番号が0でないときは、真ん中の0を変更する!! #
  
  flag = 0
  while task:
    while task:
      c, p, prev = heappop(task)    
      if visited[p] == 0:
        break  
      if len(task) == 0:
        flag = 1
    if flag == 1:
      break
    #print(task)
    visited[p] = 1
    min_cost[p] = c
    prev_points[p] = prev
  
    for j, c_ad in I[p]: #制約が入るときはここに追加
      if visited[j] == 1: continue
      #print(p//(N*A_m+1),p%(N*A_m+1),j//(N*A_m+1),j%(N*A_m+1),c_ad)
      cost_next = next_cost(I, p, j, c, c_ad)
      if cost[j] > cost_next:
        cost[j] = cost_next
        heappush(task, (cost_next, j, p))

  return (min_cost, prev_points)

def next_cost(I, p, j, c, c_ad): # !!現在の点pから次の点jへのコストを計算する方法を記入!! #  
#c:点pにつくまでに払ったコスト、c_ad:次回追加されるコスト#
  return c + c_ad

min_cost, prev_points = dijkstra(I)

for i in range(1, N):
  print(min(min_cost[i*(N*A_m+1):(i+1)*(N*A_m+1)]))

def main():    
    import heapq
    
    n, m, s = list(map(int, input().split()))
    if s >= 2500:
        s = 2499
    
    edges = [[] for _ in range(n)]
    for _ in range(m):
        from_, to, cost, time = list(map(int, input().split()))
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))
    
    banks = []
    for i in range(n):
        coin, time = list(map(int, input().split()))
        banks.append((coin, time))
    
    INF = float('INF')
    DP = [[INF] * 2500 for _ in range(n)]
    ans = [INF] * n
    
    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
    
    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin >= 2500:
            new_coin = 2499
        push_todo(node, new_coin, current_time+time)
    
    todo = [(0, 0, s)]
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time >= DP[node][current_coin]:
            continue
    
        if current_time < ans[node]:
            ans[node] = current_time
    
        DP[node][current_coin] = current_time
        charge(node, current_coin, current_time)
    
        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)
    
    for a in ans[1:]:
        print(a)


def __starting_point():
    main()

__starting_point()

import sys
input =sys.stdin.readline
import heapq

def dijkstra(edge, start):
    n = len(edge)
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist

n, m, s = map(int, input().split())
G = [[] for _ in range(n)]
if s >= 2500:
  for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append((v, b))
    G[v].append((u, b))
  L = dijkstra(G, 0)
else:
  for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append((v, a, b))
    G[v].append((u, a, b))
  CD = [list(map(int, input().split())) for _ in range(n)]
  edge = [[] for _ in range(n*2500)]
  for i in range(n):
    c, d = CD[i]
    for k in range(2500):
      for v, a, b in G[i]:
        if k >= a:
          edge[2500*i+k].append((2500*v+(k-a), b))
      if k+c < 2500:
        edge[2500*i+k].append((2500*i+(k+c), d))
  dist = dijkstra(edge, s)
  L = [0]*n
  for i in range(n):
    L[i] = min(dist[2500*i:2500*(i+1)])
print(*L[1:], sep="\n")

#!python3

from heapq import heappop, heappush


INF = 10 ** 18

# input
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)]


def solve(link):
    ans = {}
    lim = 50 * (N - 1)
    w = [[INF] * (lim + 1) for _ in range(N)]

    # (time, node, silver)
    hq = [(0, 0, min(S, lim))]
    while hq:
        t, v, s = heappop(hq)
        if t > w[v][s]:
            continue
        if v not in ans:
            ans[v] = t
            if len(ans) == N:
                break
        
        # buy
        if s < lim:
            c, d = CD[v]
            new_s = min(lim, s + c)
            new_t = t + d
            if new_t < w[v][new_s]:
                w[v][new_s] = new_t
                heappush(hq, (new_t, v, new_s))
        
        # move
        for u, a, b in link[v]:
            if s < a:
                continue
            new_s = s - a
            new_t = t + b
            if new_t < w[u][new_s]:
                w[u][new_s] = new_t
                heappush(hq, (new_t, u, new_s))
        
    return ans


def main():
    link = [[] for _ in range(N)]
    for u, v, a, b in UVAB:
        link[u - 1].append((v - 1, a, b))
        link[v - 1].append((u - 1, a, b))
    
    ans = solve(link)
    for i in range(1, N):
        print((ans[i]))


def __starting_point():
    main()

__starting_point()

import heapq
import sys
input = sys.stdin.readline

INF = 10 ** 18

class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time

dp = []
h = []

def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))

def dijkstra(n, G, cd, start, s, max_s):
    nonlocal dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        # 両替
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))

        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)


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)]

es = [[] for i in range(n)]
max_s = 50 * (n-1)

for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))

dijkstra(n, es, cd, 0, min(max_s,s), max_s)

for i in range(1, n):
    print((min(dp[i])))




# -*- coding: utf-8 -*-
import heapq

N,M,S = list(map(int, input().rstrip().split()))
UVAB_list = [list(map(int, input().rstrip().split())) for i in range(M)]
CD_list = [list(map(int, input().rstrip().split())) for i in range(N)]
#-----

max_money = 2500
S = min(max_money, S)

# graph[current city][i] = [ (next city, coin, time) ]
graph = [None] + [ [] for _ in range(N) ]

# change[current city][i] = [ (coin, time) ]
change = [None] + [ () for _ in range(N) ]

# dp[city][money] = total time
dp = [None] + [ [float("inf")]*(max_money + 1) for _ in range(N) ]
dp[1][S] = 0


for u,v,a,b in UVAB_list:
    graph[u].append( (v,a,b) )
    graph[v].append( (u,a,b) )

for i,(c,d) in enumerate(CD_list):
    change[i+1] = (c,d)

# heap[i] = (current time, current city, current money)
heap = [ (0, 1, S) ]


while heap:
    cur_time, cur_city, cur_mone = heapq.heappop(heap)
    
    # change money at current city ---
    changed_money = cur_mone + change[cur_city][0]
    changed_time = cur_time + change[cur_city][1]
    
    if (changed_money <= max_money) and (changed_time < dp[cur_city][changed_money] ):
        dp[cur_city][changed_money] = changed_time
        heapq.heappush(heap, ( changed_time, cur_city, changed_money) )
    
    # move to next city ---
    for next_city, cost_coin, cost_time in graph[cur_city]:
        next_time = cur_time + cost_time
        next_money = min( max_money , cur_mone - cost_coin )
        
        if (cur_mone >= cost_coin) and ( next_time < dp[next_city][next_money] ):
            dp[next_city][next_money] = next_time
            heapq.heappush(heap, ( next_time, next_city, next_money) )


for row in dp[2:]:
    print(( min(row) ))


from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M, S, *I = map(int, open(0).read().split())
UVAB, CD = I[:4 * M], I[4 * M:]

R, C, V = [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    for i in range(2501 - a):
        R += [(i + a) * 51 + u, (i + a) * 51 + v]
        C += [i * 51 + v, i * 51 + u]
        V += [b, b]

for i, (c, d) in enumerate(zip(*[iter(CD)] * 2), 1):
    for j in range(2501 - c):
        R.append(j * 51 + i)
        C.append((j + c) * 51 + i)
        V.append(d)

D = dijkstra(
    csr_matrix((V, (R, C)), [2500 * 60] * 2),
    indices=min(2500, S) * 51 + 1
)

for i in range(2, N + 1):
    print(int(D[i::51].min()))

from heapq import heappop, heappush
INF = float('inf')

N, M, S = map(int,input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	U, V, A, B = map(int,input().split())
	graph[U-1].append((V-1, A, B))
	graph[V-1].append((U-1, A, B))

C, D = [0]*N, [0]*N
for i in range(N):
    c, d = map(int,input().split())
    C[i], D[i] = c, d

def Extdijkstra(start):
    nonlocal S
    N_d = len(graph)
    M = 2500

    if S >= M:
        S = M-1
    
    dist = [[INF]*M for _ in range(N_d)]
    dist[start][S] = 0
    q = [(0, S, start)]

    while q:
        d, num, v = heappop(q)
        if num+C[v] < M and d+D[v] < dist[v][num+C[v]]:  # 自己ループ
            dist[v][num+C[v]] = d+D[v]
            heappush(q, (d+D[v], num+C[v], v))
        for node, c, t in graph[v]:
            if num >= c and d + t < dist[node][num-c]:
                dist[node][num-c] = d+t
                heappush(q, (d+t, num-c, node))
    return dist

d = Extdijkstra(0)
for i in range(1, N):
	print(min(d[i]))

import math
import heapq

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

road = []
for i in range(m):
    u,v,a,b = map(int,input().split())
    road.append([u,v,a,b])

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

tree = [[] for _ in range(n+1)]

for i in range(m):  
    r = road[i]
    tree[r[0]].append([r[0],r[1],r[2],r[3]])
    tree[r[1]].append([r[1],r[0],r[2],r[3]])

least_cost = [[] for _ in range(n+1)]
for l in range(n+1):
    least_cost[l] = [math.inf]*2501

queue = []

#hwd [location, money, time]
def dijakstra(q):
    while q != []:
        hwd = heapq.heappop(q)

        if least_cost[hwd[1]][hwd[2]] > hwd[0]:
            least_cost[hwd[1]][hwd[2]] = hwd[0]
            
            for node in tree[hwd[1]]:
                # from node, to node , money, time
                if hwd[2] - node[2] >= 0:
                    heapq.heappush(q,(hwd[0]+node[3],node[1],hwd[2]-node[2]))
            if hwd[2] + change[hwd[1]-1][0] <= 2500:
                heapq.heappush(q,(hwd[0]+change[hwd[1]-1][1],hwd[1],hwd[2]+change[hwd[1]-1][0]))
    return least_cost

if s > 2500:
    s = 2500
queue.append((0,1,s))

ans = dijakstra(queue)

for i in range(2,n+1):
    print(min(ans[i]))

def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500

    N, M, S = list(map(int, input().split()))
    S = min(S, MX_AG)  # それ以上のAgは不要

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))

    exchange = []
    for _ in range(N):
        c, d = list(map(int, input().split()))
        exchange.append((c, d))

    h = [(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    # time[location][r_Ag]:=minimum_time_to_reach

    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            n_Ag = ag - fare
            if n_Ag < 0: continue
            cf = time[to][n_Ag]
            n_time = t + dt
            if cf <= n_time: continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))

        e_time = t + exchange[loc][1]
        e_Ag = ag + exchange[loc][0]
        if e_Ag > MX_AG: continue
        cf = time[loc][e_Ag]
        if cf <= e_time: continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))

    ans = (min(time[to]) for to in range(1, N))

    print(('\n'.join(map(str, ans))))


def __starting_point():
    main()

__starting_point()

N, M, S = list(map(int, input().split(" ")))
adj = [ [] for _ in range(N) ] 
convert = []
for _ in range(M) :
    u, v, a, b = list(map(int, input().split(" ")))
    adj[u-1].append( (v-1,a,b) )
    adj[v-1].append( (u-1,a,b) )

for _ in range(N) :
    c, d = list(map(int, input().split(" ")))
    convert.append( (c, d) )  

import heapq 

limit = 2500
S = min(S, limit)
h = [ (0, 0, S) ] 
ans = [  [float('inf')]*(limit+1) for _ in range(N) ]

while h != [] :
    time_consumed, city, coin = heapq.heappop(h)
    if ans[city][coin] < time_consumed:
        continue
    ans[city][coin] = time_consumed
    
    if coin + convert[city][0] < limit and ans[city][coin + convert[city][0]] > time_consumed + convert[city][1] :
        ans[city][coin + convert[city][0]] = time_consumed + convert[city][1]
        heapq.heappush(h, (time_consumed + convert[city][1], city, coin+convert[city][0] ) )

    for v, a, b in adj[city] :
        if coin - a < 0 or ans[v][coin-a] <= time_consumed+b :
            continue
        ans[v][coin-a] = time_consumed+b
        heapq.heappush( h, (time_consumed+b, v, coin-a) )
    
for i in range(1, N) :
    print((min(ans[i])))


def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500

    N, M, S = map(int, input().split())
    S = min(S, MX_AG)  # それ以上のAgは不要

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))

    exchange = []
    for _ in range(N):
        c, d = map(int, input().split())
        exchange.append((c, d))

    h = [(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    # time[location][r_Ag]:=minimum_time_to_reach

    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            n_Ag = ag - fare
            if n_Ag < 0: continue
            cf = time[to][n_Ag]
            n_time = t + dt
            if cf <= n_time: continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))

        e_time = t + exchange[loc][1]
        e_Ag = ag + exchange[loc][0]
        if e_Ag > MX_AG: continue
        cf = time[loc][e_Ag]
        if cf <= e_time: continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))

    ans = (min(time[to]) for to in range(1, N))

    print(*ans, sep='\n')


def __starting_point():
    main()

__starting_point()

import numpy as np
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import shortest_path
M=49*50+1
n,m,s=map(int,input().split())
s=min(s,M-1)
G=lil_matrix((n*M,n*M))
for _ in range(m):
    a,b,silver,time=map(int,input().split())
    a-=1
    b-=1
    for i in range(silver,M):
        G[a*M+i,b*M+i-silver]=time
        G[b*M+i,a*M+i-silver]=time
for i in range(n):
    silver,time=map(int,input().split())
    for j in range(M-1):
        G[i*M+j,i*M+min(j+silver,M-1)]=time
G=G.tocsr()
G=shortest_path(G,method='D',indices=s)

for i in range(1,n):
    ans=np.min(G[i*M:i*M+M])
    print(int(ans))

from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline

DEBUG = False
INF = float('inf')
MAX_N = 50
MAX_A = 50

N, M, S = list(map(int, input().split()))
U = []
V = []
A = []
B = []
C = []
D = []

connect = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)
    connect[u-1].append([v-1, a, b])
    connect[v-1].append([u-1, a, b])
for _ in range(N):
    c, d = list(map(int, input().split()))
    C.append(c)
    D.append(d)

if DEBUG:
    print(("U: {}".format(U)))
    print(("V: {}".format(V)))
    print(("A: {}".format(A)))
    print(("B: {}".format(B)))
    print(("C: {}".format(C)))
    print(("D: {}".format(D)))
    print(("connect: {}".format(connect)))

MAX_N = N
MAX_A = max(A)
MAX_MONEY = MAX_N * MAX_A
S = min(S, MAX_MONEY-1)

node = [INF for _ in range(MAX_MONEY * N)]
hq = []
heappush(hq, (0, S))
while hq:
    time, current_node = heappop(hq)
    if DEBUG:
        print(("time: {}, current_node: {}, len(hq): {}".format(time, current_node, len(hq))))
    if time < node[current_node]:
        node[current_node] = time
    else:
        continue
    index_city = current_node // MAX_MONEY
    money = current_node % MAX_MONEY
    if DEBUG:
        print(("money: {}".format(money)))

    for index_next_city, a, b in connect[index_city]:
        if money >= a and time+b < node[index_next_city*MAX_MONEY + money-a]:
            heappush(hq, (time+b, index_next_city*MAX_MONEY + money-a))
    if money < MAX_MONEY-1:
        heappush(hq, (time+D[index_city], min(money+C[index_city], MAX_MONEY-1)+MAX_MONEY*index_city))

for i in range(1,N):
    if DEBUG:
        print(("node{}: {}".format(i, node[MAX_MONEY*i:MAX_MONEY*(i+1)])))
    print((min(node[MAX_MONEY*i:MAX_MONEY*(i+1)])))


from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
x=51
r=range(0,x**3,x)
for u,v,a,b in t[:m]:
 for i in r:D+=i+a*x+u,i+v,b,i+a*x+v,i+u,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:D+=j+i,j+c*x+i,d
d=csgraph.dijkstra(csr_matrix((D[2::3],(D[::3],D[1::3])),[j*2]*2),1,min(j,s*x)+1)
for i in range(2,n+1):print(int(min(d[i::x])))

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: list(map(int, stdin.readline().split()))
nl = lambda: list(map(int, stdin.readline().split()))

n, m, s = nm()
N = n * 3001
G = [list() for _ in range(N)]
for _ in range(m):
    u, v, a, b = nm()
    u -= 1; v -= 1
    for j in range(0, N, n):
        if v + j - a * n >= 0:
            G[u + j].append((v + j - a * n, b))
        if u + j - a * n >= 0:
            G[v + j].append((u + j - a * n, b))
for u in range(n):
    c, d = nm()
    for j in range(0, N, n):
        G[u + j].append((min(u + j + c * n, u + N - n), d))

import heapq as hq

def dijkstra(G, s, t=None):
    """
    G[v] = [(x1, c1), (x2, c2), ...]
    """
    dist = [-1]*len(G)
    dist[s] = 0
    q = [(0, s)]
    while q:
        d, v = hq.heappop(q)
        if d > dist[v]: continue
        for x, c in G[v]:
            if dist[x] < 0 or dist[x] > d + c:
                dist[x] = d + c
                hq.heappush(q, (d + c, x))
    if t is None:
        return dist
    else:
        return dist[t]

dist = dijkstra(G, min(s, 3000) * n)
for i in range(1, n):
    print((min(dist[i::n])))


import collections
import heapq

INF = 10 ** 18
MAX_S = 50*50+5

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, cost, t): self.to, self.cost, self.t = to, cost, t

def main():
    N, M, S = ZZ()
    C, D = [0]*(N+1), [0]*(N+1)
    E = collections.defaultdict(list)
    dist = [[INF] * (MAX_S+1) for _ in range(N+1)]

    for _ in range(M):
        u, v, a, b = ZZ()
        E[u].append(edge(v, a, b))
        E[v].append(edge(u, a, b))

    for i in range(1, N+1): C[i], D[i] = ZZ()

    S = min(S, MAX_S)
    dist[1][S] = 0

    que = list()
    heapq.heapify(que)
    heapq.heappush(que, [dist[1][S], 1, S])

    while que:
        x, v, s = heapq.heappop(que)
        if dist[v][s] < x: continue

        #遷移
        ns = min(s+C[v], MAX_S)
        if dist[v][ns] > x + D[v]:
            dist[v][ns] = x + D[v]
            heapq.heappush(que, [x+D[v], v, ns])

        #遷移
        for e in E[v]:
            if s - e.cost < 0: continue
            if dist[e.to][s-e.cost] > x + e.t:
                dist[e.to][s-e.cost] = x + e.t
                heapq.heappush(que, [x+e.t, e.to, s-e.cost])

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

def __starting_point():
    main()

__starting_point()

N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

S=min(S,2450)
di=[inf]*2451*N
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金
    if t>di[v]:
        continue

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    c=min(c,2450-s)
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=min(di[i*2451:(i+1)*2451])
    print(m)

from heapq import heappush, heappop
def main():
    N, M, S = list(map(int, input().split()))
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u].append((v, a, b))
        G[v].append((u, a, b))
    CD = [list(map(int, input().split())) for _ in range(N)]
    distance = [[1<<62]*2501 for _ in range(N)]
    q = [(0, 0, min(S, 2500))]
    distance[0][min(S, 2500)] = 0
    while q:
        d, v, vs = heappop(q)
        if distance[v][vs] != d:
            continue

        vc, vd = CD[v]
        ud = d + vd
        us = vs + vc
        if us > 2500:
            us = 2500
        if distance[v][us] > ud:
            distance[v][us] = ud
            heappush(q, (ud, v, us))

        for u, fee, b in G[v]:
            if fee > vs:
                continue
            ud = d + b
            us = vs - fee
            if us > 2500:
                us = 2500
            if distance[u][us] > ud:
                distance[u][us] = ud
                heappush(q, (ud, u, us))
    print(("\n".join(str(min(d)) for d in distance[1:])))

main()


import sys
from heapq import heappush, heappop
import numpy as np

def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():

    def dijkstra(s):
        def push(v, s, x):
            if s < 0: 
                return
            if dist[v, s] <= x:
                return
            dist[v, s] = x
            heappush(que, (x, v, s))
        
        inf = 10**18
        dist = np.full((n, MAX_S+1), inf, dtype=int)
        # time, remain, node
        que = []
        push(0, s, 0)
        while que:
            x, v, s = heappop(que)
            if dist[v, s] < x:
                continue
            ns = min(s+c[v], MAX_S)
            push(v, ns, x+d[v])
            for nv, a, b in adj[v]:
                push(nv, s-a, x+b)
        return np.min(dist, axis=1)

    n, m, s = mi()
    adj = [[] for i in range(n)]
    MAX_S = 0
    for i in range(m):
        u, v, a, b = mi()
        u -= 1
        v -= 1
        adj[u].append((v, a, b))
        adj[v].append((u, a, b))
        MAX_S = max(MAX_S, a)
    MAX_S *= n-1
    s = min(s, MAX_S)
    c, d = [0]*n, [0]*n
    for i in range(n):
        c[i], d[i] = mi()
    ans = dijkstra(s)
    print(*ans[1:], sep='\n')


def __starting_point():
    main()
__starting_point()

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)


from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = map(int, input().split())
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    # dijkstra (time, vertex, money)
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        for nv, (a, b) in to[now].items():
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        # exchange gold with silver
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

def __starting_point():
    main()
__starting_point()