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
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
graph = [{} for _ in range(N)]
for _ in range(M):
    u, v, a, t = mapint()
    graph[u-1][v-1] = (a, t)
    graph[v-1][u-1] = (a, t)

change = [list(mapint()) for _ in range(N)]
from heapq import heappop, heappush

Q = [(0, min(2500, S), 0)]
dist = [[10**18]*2501 for _ in range(N)]
dist[0][min(2500, S)] = 0

while Q:
    t, s, v = heappop(Q)
    rate, change_time = change[v]
    if s<2500 and dist[v][min(2500, s+rate)]>t+change_time:
        dist[v][min(2500, s+rate)] = t+change_time
        heappush(Q, (t+change_time, min(2500, s+rate), v))
    for nx in graph[v].keys():
        nx_s, nx_t = graph[v][nx]
        if nx_s<=s and dist[nx][s-nx_s]>t+nx_t:
            dist[nx][s-nx_s] = t+nx_t
            heappush(Q, (t+nx_t, s-nx_s, nx))
for i in range(1, N):
    print(min(dist[i]))

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


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

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

maxcoin = 0

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

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

class Heap1D:
    def __init__(self, shift=20):
        self.shift = shift
        self.data = []
        self.mask = (1<<shift)-1
    
    def push(self, x):
        a, b = x
        heapq.heappush(self.data, (a<<self.shift) | b)
    
    def pop(self):
        a = heapq.heappop(self.data)
        b = a & self.mask
        a >>= self.shift
        return a,b
      
    def __len__(self):
        return len(self.data)
      
def dijkstra(start = 0):
    d = [INF for i in range(len(G))]
    d[start] = 0
    que = Heap1D()
    que.push((0, start))

    while len(que):
        p = que.pop()
        v = p[1]
        if d[v] < p[0]:
            continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                que.push((d[u], u))
    return d

N,M,S=map(int,input().split())
edges = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(N)]
INF= 10**15
mod=55

mmax = sum([edges[i][2] for i in range(M)])
if S>mmax:
  S = mmax

G=[{} for _ in range((mmax+1)*mod+N+1)]
for i in range(M):
  u,v,a,b=edges[i]
  for p in range(a,mmax+1):
    G[u+p*mod][v+(p-a)*mod] = b
    G[v+p*mod][u+(p-a)*mod] = b
    
for i in range(N):
  c,d=cd[i]
  for p in range(mmax+1-c):
    G[i+1+p*mod][i+1+(p+c)*mod] = d
  
start = 1+S*mod
d = dijkstra(start)

ans=[INF]*(N+1)
for i in range(2,len(G)+1):
  v = i%mod
  if v>N or v<2:continue
  ans[v] = min(ans[v],d[i])
  
print(*ans[2:])

Solution (Python):
import heapq

N, M, S = map(int, input().split())
Map = [[] for _ in range(N)]
Ans = [[float('inf')] * 2500 for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    Map[u].append((v, a, b))
    Map[v].append((u, a, b))

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

Q = []
heapq.heappush(Q, (0, 0, min(2499, S))) 
Ans[0][min(2499, S)] = 0
while Q:
    time, where, money = heapq.heappop(Q)
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        if Ans[nex][min(2499, money - cost)] > time + take:
            Ans[nex][min(2499, money - cost)] = time + take
            heapq.heappush(Q, (time + take, nex, money - cost))

for a in Ans[1:]:
    print(min(a))

Solution (Python):
import heapq
def dijkstra(s, n, g, d): 
    INF = 10**18
    d[s] = 0
    que = [] 
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue 
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                heapq.heappush(que, (d[next_v], next_v))
    return d


def main():
    n,m,s = map(int, input().split())
    
    g = {}
    dist = {}
    for i in range(n):
        for j in range(2501):
            g[(i,j)] = []
            dist[(i,j)] = 10**18
    for _ in range(m):
        u,v,a,b = map(int, input().split())
        u-=1
        v-=1
        for j in range(2501):
            if j < a: continue
            g[(u,j)].append(((v,j-a),b))
            g[(v,j)].append(((u,j-a),b))
            
            

    for i in range(n):
        c,d = map(int, input().split())
        for j in range(2501):
            maxc = min(2500,j+c)
            g[(i,j)].append(((i,maxc), d))

    sc = min(2500,s)
    s = (0,sc)
    dist = dijkstra(s, n*2501+1, g, dist)
    
    for i in range(1,n):
        ans = 10**18
        for j in range(2501):
            ans = min(ans, dist[(i,j)])
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq
def dijkstra(s, n, g): 
    INF = 10**18
    d = [INF] * n
    d[s] = 0
    que = [] 
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue 
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                heapq.heappush(que, (d[next_v], next_v))
    return d


def main():
    n,m,s = map(int, input().split())
    g = [ [] for _ in range(n*2501+1)]
    for _ in range(m):
        u,v,a,b = map(int, input().split())
        u-=1
        v-=1
        for j in range(2501):
            if j < a: continue
            g[u*2501+j].append((v*2501+j-a,b))
            g[v*2501+j].append((u*2501+j-a,b))


    cdl = [(-1,-1)]
    for i in range(n):
        c,d = map(int, input().split())
        for j in range(2501):
            maxc = min(2500,j+c)
            g[i*2501+j].append((i*2501+maxc,d))

    s = min(2500,s)
    dist = dijkstra(s, n*2501+1, g)
    
    for i in range(1,n):
        ans = min(dist[i*2501:i*2501+2500])
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

def dijkstra(s,n):
    hq = [(0, s)]
    heapq.heapify(hq) 
    cost = [float('inf')] * n 
    cost[s] = 0 
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: 
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost


e = [[] for _ in range(10000*(n+1))]
for i in range(n):
    c,d=cd[i]
    for j in range(2500):
        e[10000*i+j].append((d,10000*i+min(j+c,2500)))
    
for i in range(m):
    u,v,a,b=uvab[i]
    u,v = u-1, v-1
    for j in range(2500):
        if j-a>=0:
            e[10000*v+j].append((b,10000*u+j-a))
            e[10000*u+j].append((b,10000*v+j-a))

s=min(2499,s)

lst=dijkstra(s,10000*(n+1))

for i in range(1,n):
    ans=float('inf')
    for j in range(2500):
        ans=min(ans,lst[10000*i+j])
    print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N, M, S = map(int, input().split())
adj = [[] for _ in range(N)]
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append((v, a, b))
    adj[v].append((u, a, b))
C = [0] * N
D = [0] * N
for i in range(N):
    C[i], D[i] = map(int, input().split())

MAX = 50 * 50 + 5
dp = [[INF] * (MAX + 1) for _ in range(N)]
q = []
def push(x, v, s):
    if s < 0:
        return
    if dp[v][s] <= x:
        return
    dp[v][s] = x
    heappush(q, (x, v, s))
s = min(MAX, S)
push(0, 0, s)
while len(q) > 0:
    x, v, s = heappop(q)
    if dp[v][s] != x:
        continue
    
    ns = min(s + C[v], MAX)
    push(x + D[v], v,  ns)
    
    for u in adj[v]:
        push(x + u[2], u[0], s - u[1])

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

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

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

Solution (Python):
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:
    u,v=u-1,v-1
    g[u].append([v,a,b])
    g[v].append([u,a,b])


from heapq import heappop,heappush
inf=float('inf')
maxs=50*m
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]))

Solution (Python):
from heapq import heappush, heappop
def main():
    N, M, S = map(int, input().split())
    G = [[] for _ in range(N)]
    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)]
    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()

Solution (Python):
import heapq

N, M, S = map(int, input().split())
Cost = [[] for _ in range(N)]
Change = [[0]*2 for _ in range(N)]
A_m = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    A_m = max(A_m, a)
    Cost[u-1].append([v-1, a, b])
    Cost[v-1].append([u-1, a, b])
for i in range(N):
    c, d = map(int, input().split())
    Change[i][0] = c
    Change[i][1] = d
if S > A_m*N:
    S = A_m*N

def dijkstra(N, start, Cost, Change):
    rich = [[] for _ in range(N+1)]
    Ans = [10**18]*N
    Ans[0] = 0
    minHeap = []
    used = [[10**18]*(A_m*N + 1) for _ in range(N)]
    used[start][S] = 0
    heapq.heappush(minHeap, (0, S, start))
    while minHeap:
        (c, hold, current) = heapq.heappop(minHeap)
        if rich[current] and rich[current][-1] >= hold:
            continue
        rich[current].append(hold)
        j = 1
        for i in range(N):
            if Ans[i] > c:
                j = 0
                break
        if j == 1:
            break
        for P in Cost[current]:
            road, a, b = P
            if hold >= a:
                if used[road][hold - a] > c + b:
                    used[road][hold - a] = c + b
                    heapq.heappush(minHeap, (c + b, hold - a, road))
                if Ans[road] > c + b:
                    Ans[road] = c + b
        if hold + Change[current][0] <= A_m*N:
            if used[current][hold + Change[current][0]] > c + Change[current][1]:
                heapq.heappush(minHeap, (c + Change[current][1], hold + Change[current][0], current))
    return Ans

T = dijkstra(N, 0, Cost, Change)
for i in T[1:]:
    print(i)

Solution (Python):
import heapq


def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) 
    cost = [float('inf')] * ((maxsilver+1)*n) 
    cost[s] = 0 
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: 
            continue
        for d, w in e[v]:
            tmp = d + cost[v]
            if tmp < cost[w]:
                cost[w] = tmp
                heapq.heappush(hq, (tmp, w))
    return cost

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

u,v,a,b = [0]*m,[0]*m,[0]*m,[0]*m 
c,d = [0]*n,[0]*n 
for i in range(m):
    u[i],v[i],a[i],b[i] = list(map(int,input().split()))
for i in range(n):
    c[i],d[i] = list(map(int,input().split()))

maA = max(a)
maxsilver = maA*(n-1)
p = (maxsilver+1) * n

e = [[] for i in range(p)]

for i in range(n):
    for j in range(maxsilver+1):
        e[i*(maxsilver+1) + j].append((d[i], i*(maxsilver+1) + min(j+c[i], maxsilver)))

for i in range(m):
    for j in range(a[i],maxsilver+1):
        e[(u[i]-1)*(maxsilver+1) + j].append((b[i], (v[i]-1)*(maxsilver+1) + j-a[i]))
        e[(v[i]-1)*(maxsilver+1) + j].append((b[i], (u[i]-1)*(maxsilver+1) + j-a[i]))



d = dijkstra(min(s,maxsilver))
for i in range(1,n):
    ans = float("inf")
    x = [0]*(maxsilver+1)
    for j in range(maxsilver+1):
        x[j] =  d[i*(maxsilver+1)+j]
    heapq.heapify(x)
    ans = heapq.heappop(x)
    print(ans)

Solution (Python):

from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))
def make_array(dim, type=int): return defaultdict(lambda: defaultdict(type))


INF=10**20
def main():
    N,M,S=mi()
    
    G = [[] for _ in range(N+1) ]
    T = [None] * M
    for i in range(M):
        u,v,a,b=mi()
        T[i] = (u,v,a,b)
        G[u].append((i,v,a,b)) 
        G[v].append((i,u,a,b))
        

    
    C = []
    D = []
    for i in range(N):
        c,d = mi()
        C.append(c)
        D.append(d)
    
    cost = defaultdict(lambda: defaultdict(int))
    E = defaultdict(lambda: [])
    for i in range(0,2501):
        for track in T:
            u,v,a,b = track
            if i-a < 0: continue
            cost[(u,i)][(v,i-a)] = b
            cost[(v,i)][(u,i-a)] = b
            E[(u,i)].append((v,i-a))
            E[(v,i)].append((u,i-a))
            
        
        for j in range(N):
            c,d = C[j],D[j]
            cost[(j+1,i)][(j+1,i+c)] = d
            E[(j+1,i)].append((j+1,i+c))





    if S > 2500: S = 2500

    s = (1,S)
    hq = [(0,s)]
    heapq.heapify(hq)

    dist = defaultdict(lambda: INF)
    dist[s] = 0
    while hq: 
        d,x = heapq.heappop(hq) 
        if dist[x] < d: continue

        for e in E[x]:
            
            if dist[e] > dist[x] + cost[x][e]:
                dist[e] = dist[x] + cost[x][e]
                heapq.heappush(hq,(dist[e],e))
    
    for t in range(2,N+1):
        ans = INF
        for i in range(0,2501):
            ans = min(ans,dist[(t,i)])
        print(ans)

    
    






if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappush,heappop

N,M,S=map(int,input().split())
edges = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(N)]
INF= 10**15
mod=55

mmax = sum([edges[i][2] for i in range(M)])
if S>mmax:
  S = mmax

G=[{} for _ in range((mmax+1)*mod+N+1)]
for i in range(M):
  u,v,a,b=edges[i]
  for p in range(a,mmax+1):
    G[u+p*mod][v+(p-a)*mod] = b
    G[v+p*mod][u+(p-a)*mod] = b
    
for i in range(N):
  c,d=cd[i]
  for p in range(mmax+1-c):
    G[i+1+p*mod][i+1+(p+c)*mod] = d
    
def dijkstra(start = 0):
    
    d = [INF for i in range(len(G)+1)]
    d[start] = 0
    
    que = []
    heappush(que, (0, start))

    while len(que):
        p = heappop(que)
        v = p[1]
        
        if d[v] < p[0]:
            continue
            
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    
    return d
  
start = 1+S*mod
d = dijkstra(start)

ans=[INF]*(N+1)
for i in range(2,len(G)+1):
  v = i%mod
  if v>N or v<2:continue
  ans[v] = min(ans[v],d[i])
  
print(*ans[2:])

Solution (Python):
from heapq import heappop, heappush

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(cities,trains,S):
    N = len(cities)
    adj = [[] for _ in range(N)]

    for u,v,a,b in trains:
        u,v = u-1,v-1
        adj[u].append((v,a,b))
        adj[v].append((u,a,b))

    M = 2500
    S = min2(S,M-1)

    encode = lambda v,c: v*M+c
    decode = lambda i: (i//M,i%M)

    dist = [10**18]*(N*M)
    dist[S] = 0

    q = [(0, S)]

    while q:
        d,i = heappop(q)
        if dist[i] < d:
            continue

        v,c = decode(i)
        C,D = cities[v]

        nc = min2(c+C,M-1)
        ni = encode(v,nc)
        nd = d+D
        if dist[ni] > nd:
            dist[ni] = nd
            heappush(q, (nd, ni))

        for u,a,b in adj[v]:
            if c < a:
                continue
            ni = encode(u,c-a)
            nd = d+b
            if dist[ni] > nd:
                dist[ni] = nd
                heappush(q, (nd, ni))

    return [min(dist[v*M:v*M+M]) for v in range(N)][1:]



if __name__ == '__main__':
    N,M,S = map(int,readline().split())

    m = map(int,read().split())

    trains = list(t for _,t in zip(range(M), zip(m,m,m,m)))
    cities = list(zip(m,m))

    print(*solve(cities,trains,S), sep='\n')

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


def main():
    n, m, s = map(int, input().split())
    
    s = min(s, 2500)
    
    railway = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = 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]))
    
    
if __name__ == "__main__":
    main()

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


def main():
    n, m, s = map(int, input().split())
    
    s = min(s, 2500)
    
    railway = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = 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]))
    
    
if __name__ == "__main__":
    main()

Solution (Python):
class Graph:
    class Edge:
        def __init__(self, to, cost, fare):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost, self.fare = to, cost, fare

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        self.fare_max = 0
        for x, y, cost, fare in edges:
            self.add_edge(x, y, cost, fare)
            if fare > self.fare_max:
                self.fare_max = fare

    def add_edge(self, x, y, cost, fare):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost, fare))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost, fare))
        if fare > self.fare_max:
            self.fare_max = fare

    def cut(self, x):
        return min2(x, self.fare_max * (self.n - 1))

    def dijkstra(self, start, S, INF=10**18):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        備考: heqpq の比較のための key は第一引数である点に注意（ =　heappush(heapq, (key,value))　）
        """
        res = [[INF] * (self.fare_max*self.n+1) for _ in  range(self.n)]
        if self.decrement:
            start -= 1
        money = self.cut(S)
        res[start][money] = 0
        next_set = [(0, start, money)]
        while next_set:
            dist, p, money = heappop(next_set)
            if res[p][money] < dist:
                continue
            for edge in self.edges[p]:
                q, cost, fare = edge.to, edge.cost, edge.fare
                temp_d = dist + cost
                if temp_d < res[q][self.cut(money-fare)] and money >= fare:
                    res[q][self.cut(money-fare)] = temp_d
                    heappush(next_set, (temp_d, q, self.cut(money - fare)))
        if self.decrement:
            return [[0]] + res
        else:
            return res

def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y





import sys
input = sys.stdin.readline
from heapq import *
INF = 10**18  

C, D = [], []
N, M, S = map(int, input().split())

graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, fare, cost = map(int, input().split())
    graph.add_edge(x, y, cost, fare)
for i in range(1,N+1):
    fare, cost = map(int, input().split())
    graph.add_edge(i,i, cost, -fare)
d = graph.dijkstra(1,S,INF=INF)
for i in range(2,N+1):
    print(min(d[i]))