Problem:
 Score : 500 points    Problem Statement  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 1 3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5      Sample Output 1 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.        Sample Input 2 4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4      Sample Output 2 5
5
7  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 4 in 7 minutes, as follows:   At the exchange counter in City 1 , exchange 2 gold coins for 6 silver coins in 2 minutes.  Use the 2 -nd railroad to move from City 1 to City 3 in 4 minutes.  Use the 4 -th railroad to move from City 3 to City 4 in 1 minutes.        Sample Input 3 6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1      Sample Output 3 1
9003
14606
16510
16576  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 6 in 16576 minutes, as follows:   Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.  At the exchange counter in City 2 , exchange 3 gold coins for 3 silver coins in 9000 minutes.  Use the 1 -st railroad to move from City 2 to City 1 in 1 minute.  Use the 2 -nd railroad to move from City 1 to City 3 in 1 minute.  At the exchange counter in City 3 , exchange 8 gold coins for 8 silver coins in 5600 minutes.  Use the 2 -nd railroad to move from City 3 to City 1 in 1 minute.  Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.  Use the 3 -rd railroad to move from City 2 to City 4 in 1 minute.  At the exchange counter in City 4 , exchange 19 gold coins for 19 silver coins in 1900 minutes.  Use the 3 -rd railroad to move from City 4 to City 2 in 1 minute.  Use the 1 -st railroad to move from City 2 to City 1 in 1 minute.  Use the 2 -nd railroad to move from City 1 to City 3 in 1 minute.  Use the 4 -th railroad to move from City 3 to City 5 in 1 minute.  At the exchange counter in City 5 , exchange 63 gold coins for 63 silver coins in 63 minutes.  Use the 4 -th railroad to move from City 5 to City 3 in 1 minute.  Use the 2 -nd railroad to move from City 3 to City 1 in 1 minute.  Use the 5 -th railroad to move from City 1 to City 6 in 1 minute.        Sample Input 4 4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7      Sample Output 4 1
3
5  The railway network in this input is shown in the figure below:        Sample Input 5 2 1 0
1 2 1 1
1 1000000000
1 1      Sample Output 5 1000000001  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 2 in 1000000001 minutes, as follows:   At the exchange counter in City 1 , exchange 1 gold coin for 1 silver coin in 1000000000 minutes.  Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.

Solution (Python):
import sys,math,copy,queue,itertools,bisect,collections
from heapq import *
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
INF = 10**15

N,M,S = LI()
if S > N * 50:
    S = N * 50
root = [[] for _ in range(N)]
for _ in range(M):
    u,v,a,b = LI()
    root[u-1].append((v-1,a,b))
    root[v-1].append((u-1,a,b))
city = [LI() for _ in range(N)]

dp = [[INF] * (N*50+1) for _ in range(N)]
dp[0][S] = 0

hq = [[0,0,S]]
heapify(hq)

while hq:
    tm,pos,coin = heappop(hq)

    c = coin
    t = tm
    if c < N * 50:
        c += city[pos][0]
        c = min(c, N * 50)
        t += city[pos][1]
        if dp[pos][c] > t:
            dp[pos][c] = t
            heappush(hq,[t,pos,c])

    for p,a,b in root[pos]:
        c = coin - a
        if c >= 0:
            if dp[p][c] > tm + b:
                dp[p][c] = tm + b
                heappush(hq,[tm+b,p,c])

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

Solution (Python):
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 = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
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_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")

Solution (Python):
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 = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0


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

Solution (Python):
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


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



for i in range(N):
    c,d = map(int,input().split())
    for j in range(Ns): 
        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)

Solution (Python):
import heapq

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

edges = {i: [] for i in range(2501 * N - 1)}

for i in range(M):
    U, V, A, B = map(int, input().split(" "))
    edges[U - 1].append((V - 1, A, B))
    edges[V - 1].append((U - 1, A, B))

exchange_edges = {}
for i in range(N):
    C, D = map(int, input().split(" "))
    exchange_edges[i] = (C, D)

dist = [[-1 for _ in range(2501)] for _ in range(N)]
que = []
heapq.heappush(que, (0, 0, min(S, 2500)))

while que:
    time, now, s = heapq.heappop(que)
    if dist[now][s] != -1:
        continue
    dist[now][s] = time
    
    for (to, a, b) in edges[now]:
        if a > s or dist[to][s - a] != -1:
            continue
        heapq.heappush(que, (time + b, to, s - a))

    
    (silv, t) = exchange_edges[now]
    if s + silv <= 2500 and dist[now][silv + s] == -1:
        heapq.heappush(que, (time + t, now, s + silv))

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

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

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

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

x=2501

gg=[[[] for i in range(x)] for i in range(n)]
for i in range(n):
    for j in range(x-1):
        
        y=j+c[i][0]
        if y>=x-1:
            y=x-1
        gg[i][j].append((i,y,c[i][1]))


for i in range(1,x):
    for u,v,a,b in g:
        u-=1
        v-=1
        
        if i-a>=0:
            gg[v][i].append((u,i-a,b))
            gg[u][i].append((v,i-a,b))






from heapq import heappush, heappop

def dijkstra(edges, size, source,gold):
    
    
    
    distance = [[float('inf')]*x for i in range(n)]
    distance[source][gold] = 0
    visited = [[False]*x for i in range(n)]
    pq = []
    heappush(pq, (0, source,gold))
    while pq:
        dist_v, u,v = heappop(pq)
        visited[u][v] = True
        for u,v, weight in edges[u][v]:
            if not visited[u][v]:
                new_dist = dist_v + weight
                if distance[u][v] > new_dist:
                    distance[u][v] = new_dist
                    heappush(pq, (new_dist, u,v))
    return distance
s=min(2500,s)
ans=dijkstra(gg,n,0,s)

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

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

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

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

x=2501

gg=[[[] for i in range(x)] for i in range(n)]
for i in range(n):
    for j in range(x-1):
        
        y=j+c[i][0]
        if y>=x-1:
            y=x-1
        gg[i][j].append((i,y,c[i][1]))


for i in range(1,x):
    for u,v,a,b in g:
        u-=1
        v-=1
        
        if i-a>=0:
            gg[v][i].append((u,i-a,b))
            gg[u][i].append((v,i-a,b))






from heapq import heappush, heappop

def dijkstra(edges, size, source,gold):
    
    
    
    distance = [[float('inf')  for i in range(x)] for i in range(n)]
    distance[source][gold] = 0
    visited = [[False  for i in range(x)] for i in range(n)]
    pq = []
    heappush(pq, (0, source,gold))
    while pq:
        dist_v, u,v = heappop(pq)
        visited[u][v] = True
        for u,v, weight in edges[u][v]:
            if not visited[u][v]:
                new_dist = dist_v + weight
                if distance[u][v] > new_dist:
                    distance[u][v] = new_dist
                    heappush(pq, (new_dist, u,v))
    return distance
s=min(2500,s)
ans=dijkstra(gg,n,0,s)

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

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

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

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

x=2501

gg=[[] for i in range(n*x)]
for i in range(n):
    for j in range(x-1):
        
        y=j+c[i][0]
        if y>=x-1:
            y=x-1
        gg[i*x+j].append((i*x+y,c[i][1]))


for i in range(1,x):
    for u,v,a,b in g:
        u-=1
        v-=1
        
        if i-a>=0:
            gg[v*x+i].append((u*x+i-a,b))
            gg[u*x+i].append((v*x+i-a,b))





from heapq import heappush, heappop

def dijkstra(edges, size, source):
    
    
    
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance
s=min(s,2500)
ans=dijkstra(gg,n*x,s)

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

Solution (Python):

import sys
import heapq
INF = 10**20

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

def ic(i,c):
    
    return i+c*50


MAX_S = 0
for _,_,a,_ in UVAB:
    MAX_S = max(MAX_S, a)
MAX_S *= N
S = min(S, MAX_S)
MAX_N = ic(N-1, MAX_S) + 1
edge = [[] for _ in range(MAX_N)]

for u,v,a,b in UVAB:
    
    for c in range(a,MAX_S+1):
        edge[ic(u-1,c)].append([ic(v-1,c-a),b])
        edge[ic(v-1,c)].append([ic(u-1,c-a),b])

for i in range(N):
    
    ci = CD[i][0]
    di = CD[i][1]
    for c in range(MAX_S):
        edge[ic(i,c)].append([ic(i,min(c+ci,MAX_S)),di])



def dijkstra(S, N, Edge):
    
    
    
    
    INF = 10**20
    dist = [INF]*N
    dist[S] = 0
    que = [[0, S]]
    heapq.heapify(que)
    
    while que:
        c, v = heapq.heappop(que)
        if dist[v] < c: continue

        for nv, nc in Edge[v]:
            if c+nc < dist[nv]:
                dist[nv] = c+nc
                heapq.heappush(que, [c+nc, nv])
    
    return dist

dist = dijkstra(ic(0, S), MAX_N, edge)
for i in range(1,N):
    ans = INF
    for c in range(MAX_S):
        ans = min(ans, dist[ic(i,c)])
    print(ans)

Solution (Python):
import heapq

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

graph = [[] for _ in range(N)]
for _ in range(M):
	u, v, A, B = 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 = 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:

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

Solution (Python):
from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i 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))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 
lasttime=[[10**15]*2501 for i in range(n)]
lasttime[0][min(2500,s)]=0
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        nexttime,nextsilver=time+costtime,silver-costmoney
        if costmoney<=silver and lasttime[atnode][nextsilver]>nexttime:
            heappush(hp,(nexttime,nextsilver,atnode))
            lasttime[atnode][nextsilver]=min(lasttime[atnode][nextsilver],nexttime)

    nexttime,nextsilver=time+d[node],min(silver+c[node],2500)
    if silver!=2500 and lasttime[node][nextsilver]>nexttime:
        heappush(hp,(nexttime,min(silver+c[node],2500),node))
        lasttime[node][nextsilver]=min(lasttime[node][nextsilver],nexttime)
        
print(*mintimes[1:],sep="\n")

Solution (Python):
from heapq import heappop, heappush
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


PATH = [[] for _ in range(N + 1)]
CHANGES = [None] * (N + 1)

for _ in range(M):
    U, V, A, B = map(int, input().split())
    PATH[U].append((V, A, B))
    PATH[V].append((U, A, B))

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

Q = []
INF = float("inf")
TIME = [[INF] * 2501 for _ in range(N + 1)]
USED = [[False] * 2501 for _ in range(N + 1)]

Q.append((0, 1, S))
TIME[1][S] = 0

while Q:
    t, u, g = heappop(Q)

    
    
    if g < 2500:
        c, d = CHANGES[u]
        ng = min(g + c, 2500)
        nt = t + d

        if nt < TIME[u][ng]:
            TIME[u][ng] = nt
            heappush(Q, (nt, u, ng))

    
    for v, a, b in PATH[u]:
        if g < a:
            continue

        ng = g - a
        nt = t + b
        if nt < TIME[v][ng]:
            TIME[v][ng] = nt
            heappush(Q, (nt, v, ng))

ANS = [min(x) for x in TIME[2:]]
print("\n".join(map(str, ANS)))

Solution (Python):
import heapq
import sys
def dijkstra(e,dist,s,used):
  q=[]
  heapq.heappush(q,(0,0,s))
  while q:
    d,x,m=heapq.heappop(q)
    if not used[x][m]:
      continue
    dist[x][m]=d
    used[x][m]=False
    for cost,newx,silver in e[x][m]:
      if used[newx][silver]:
        heapq.heappush(q,(dist[x][m]+cost,newx,silver))
  return dist
def main():
  input=sys.stdin.readline
  n,m,s=map(int,input().split())
  if s>2500:
    s=2500
  edge=[[[] for i in range(2501)] for _ in range(n)]
  for _ in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    for j in range(a,2501):
        edge[u][j].append((b,v,j-a))
        edge[v][j].append((b,u,j-a))
  for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i][j].append((d,i,j+c))
  dist=[[10**18]*2501 for _ in range(n)]
  used=[[True]*2501 for _ in range(n)]
  dist=dijkstra(edge,dist,s,used)
  
  
  for i in range(1,n):
    print(min(dist[i]))
if __name__=="__main__":
  main()

Solution (Python):
import heapq
import sys
input=sys.stdin.readline

def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n 
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge=heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d

N,m,s=map(int,input().split())
L=[list(map(int,input().split())) for i in range(m)]
L2=[list(map(int,input().split())) for i in range(N)]
n=N*(50*(N-1)+1)
edge=[[] for i in range(n)]
for i in range(m):
  for j in range(50*(N-1)+1):
    if j>=L[i][2]:
      edge[L[i][0]-1+N*j].append([L[i][3],L[i][1]-1+N*(j-L[i][2])])
      edge[L[i][1]-1+N*j].append([L[i][3],L[i][0]-1+N*(j-L[i][2])])
for i in range(N):
  for j in range(50*(N-1)):
    edge[i+N*j].append([L2[i][1],i+N*min(50*(N-1),j+L2[i][0])])
ans=[[] for i in range(N)]
D=dijkstra_heap(min(50*(N-1),s)*N)
for i in range(len(D)):
  ans[i%N].append(D[i])
for i in range(1,N):
  print(min(ans[i]))

Solution (Python):
import heapq
def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n 
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge=heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d

N,m,s=map(int,input().split())
L=[list(map(int,input().split())) for i in range(m)]
L2=[list(map(int,input().split())) for i in range(N)]
n=N*(50*(N-1)+1)
edge=[[] for i in range(n)]
for i in range(m):
  for j in range(50*(N-1)+1):
    if j>=L[i][2]:
      edge[L[i][0]-1+N*j].append([L[i][3],L[i][1]-1+N*(j-L[i][2])])
      edge[L[i][1]-1+N*j].append([L[i][3],L[i][0]-1+N*(j-L[i][2])])
for i in range(N):
  for j in range(50*(N-1)):
    edge[i+N*j].append([L2[i][1],i+N*min(50*(N-1),j+L2[i][0])])
ans=[[] for i in range(N)]
D=dijkstra_heap(min(50*(N-1),s)*N)
for i in range(len(D)):
  ans[i%N].append(D[i])
for i in range(1,N):
  print(min(ans[i]))

Solution (Python):
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])))

Solution (Python):
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(x*x,s)*x+1)
for i in range(2,n+1):print(int(min(d[i::x])))

Solution (Python):
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])),[8**6]*2),1,min(x*x,s)*x+1)
for i in range(2,n+1):print(int(min(d[i::x])))

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

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

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

Solution (Python):
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Solution (Python):
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
for i,(c,d)in enumerate(t[m:],1):
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

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

Solution (Python):
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
for u,v,a,b in t[:m]:
    for i in range(2501):
        R+=(i+a)*51+u,(i+a)*51+v
        C+=i*51+v,i*51+u
        D+=b,b
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501):
        R+=j*51+i,
        C+=(j+c)*51+i,
        D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Solution (Python):
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
for u,v,a,b in t[:m]:
    for i in range(2501-a):
        R+=(i+a)*51+u,(i+a)*51+v
        C+=i*51+v,i*51+u
        D+=b,b
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501-c):
        R+=j*51+i,
        C+=(j+c)*51+i,
        D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Solution (Python):
def main():
    from heapq import heappush,heappop
    (n,m,s),*t=[map(int,r.split())for r in open(0)]
    e=[[]for _ in range(8**6)]
    for u,v,a,b in t[:m]:
        for i in range(2501-a):
            e[(i+a)*51+u]+=(b,i*51+v),
            e[(i+a)*51+v]+=(b,i*51+u),
    for i,(c,d)in enumerate(t[m:],1):
        for j in range(2501-c):
            e[j*51+i]+=(d,(j+c)*51+i),
    x=[10**18]*8**6
    f=[1]*8**6
    q=[(0,min(2500,s)*51+1)]
    while q:
        c,v=heappop(q)
        if f[v]<1:continue
        x[v],f[v]=c,0
        for p,w in e[v]:
            if f[w]:heappush(q,(c+p,w))
    for i in range(2,n+1):print(min(x[i::51]))
main()

Solution (Python):
from heapq import*
(n,m,s),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*8**6)
for u,v,a,b in t[:m]:
    for i in range(2501-a):
        e[(i+a)*51+u]+=(b,i*51+v),
        e[(i+a)*51+v]+=(b,i*51+u),
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501-c):
        e[j*51+i]+=(d,(j+c)*51+i),
d=[10**18]*8**6
f=[1]*8**6
q=[(0,min(2500,s)*51+1)]
while q:
    c,v=heappop(q)
    if f[v]<1:continue
    d[v],f[v]=c,0
    for p,w in e[v]:
        if f[w]:heappush(q,(c+p,w))
for i in range(2,n+1):print(min(d[i::51]))