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

Solution (Python):
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
INF = 10**100
MAX = 2500
N, M, S = map(int, input().split())
S = min(S, MAX)
G = [[] for _ in [0]*N]
C = []
for _ in [0]*M:
    u, v, a, b = 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 = map(int, input().split())
    C.append((a, b))


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)


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

Solution (Python):
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 = map(int, input().split())
INF = 10**100
G = [[] for _ in [0]*N]
C = []

for _ in [0]*M:
    u, v, a, b = 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 = 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)

Solution (Python):
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)
INF = 10e18
MAX_V = 50
MAX_S = MAX_V*50+5

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))
cd = [list(map(int, input().split())) for _ in range(n)]



dp = [[INF]*(MAX_S+5) for _ in range(MAX_V)]   
s = min(s, MAX_S)
q = []

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

push(0, s, 0)
while q:
    x,s,v = heapq.heappop(q)
    if dp[v][s] != x: continue
    ns = min(s+cd[v][0], MAX_S)
    push(v, ns, x+cd[v][1])
    for to, a, b in g[v]:
        push(to, s-a, x+b)


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

Solution (Python):
import sys

input=sys.stdin.buffer.readline

N, M, S = map(int,input().split())
SMAX = 50 * (N-1)
S = min(S,SMAX)

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 = [tuple(map(int,input().split())) for _ in range(N)]

from heapq import heappush,heappop

q=[(0,0,S)]

while q:
    t, u, s = heappop(q)
    for nxt, a, b in way[u]:
        if s >= a:

            if dp[nxt][s-a] > t + b:
                dp[nxt][s-a] = t + b
                heappush(q,(t + b, nxt, s-a))
                
    c, d = CD[u]
    nc = min(SMAX, 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]))

Solution (Python):
import sys






N, M, S = map(int,input().split())  
S=min(S,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 = [tuple(map(int,input().split())) for _ in range(N)]

from heapq import heappush,heappop



q=[(0,0,S)]  

while q:
    t, u, s = heappop(q)  
    for nxt, a, b in way[u]:  
        if s >= a:  

            if dp[nxt][s-a] > t + b:  
                dp[nxt][s-a] = t + b  
                heappush(q,(t + b, nxt, s-a))  
                
                
                

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

Solution (Python):
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**7)
input=sys.stdin.buffer.readline
N,M,S=map(int,input().split())
S=min(S,2500)
INF=10**18
time=[[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)]
q=[(0,0,S)]
while q:
  ti,city,cur=heappop(q)
  for nxt,a,b in way[city]:
    if cur>=a:
      if time[nxt][cur-a]>ti+b:
        time[nxt][cur-a]=ti+b
        heappush(q,(ti+b,nxt,cur-a))
  c,d=CD[city]
  nc=min(2500,c+cur)
  nt=ti+d
  if nt<time[city][nc]:
    time[city][nc]=nt
    heappush(q,(nt,city,nc))
for i in range(1,N):
  print(min(time[i]))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from pprint import pprint
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

C, D = ZIP(N)
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:
    d, coin, n = heappop(q)
    if coin + C[n] < M and d+D[n] < dist[n][coin+C[n]]:
        dist[n][coin+C[n]] = d+D[n]
        heappush(q, (d+D[n], coin + C[n], n))
    for node, cnode, dnode in graph[n]:
        nd = d + dnode
        if coin >= cnode and nd < dist[node][coin-cnode]:
            dist[node][coin-cnode] = nd
            heappush(q, (nd, coin-cnode, node))

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

Solution (Python):
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    
    
    
    
    
    
    
    
    
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,M,S = isRaw()
    UVABs = [isRaw() for _ in range(M)]
    Smax = N*51 
    G = [[] for _ in range(N*Smax)]
    
    for uvab in UVABs:
        u,v,a,b = uvab
        for s in range(a*N,Smax*N,N):
            G[s+u-1].append((b,s-(a*N)+v-1))
            G[s+v-1].append((b,s-(a*N)+u-1))
    for n in range(N):
        c,d = isRaw()
        for s in range(N, Smax*N, N):
            G[s+n].append((0,s-N+n))
            if s>=c*N:
                G[s-c*N+n].append((d,s+n))
    cost = dijkstra(G,min(S,Smax-N)*N)
    return "\n".join([str(c) for c in cost[1:N]])


if __name__ == "__main__":
    print(main())

Solution (Python):
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,M,S = isRaw()
    UVABs = [isRaw() for _ in range(M)]
    Smax = N*51 
    G = [[] for _ in range(N*Smax)]
    
    for uvab in UVABs:
        u,v,a,b = uvab
        for s in range(a*N,Smax*N,N):
            G[s+u-1].append((b,s-(a*N)+v-1))
            G[s+v-1].append((b,s-(a*N)+u-1))
    for n in range(N):
        c,d = isRaw()
        for s in range(N, Smax*N, N):
            G[s+n].append((0,s-N+n))
            if s>=c*N:
                G[s-c*N+n].append((d,s+n))
    cost = dijkstra(G,min(S,Smax-N)*N)
    return "\n".join([str(c) for c in cost[1:N]])


if __name__ == "__main__":
    print(main())

Solution (Python):
from collections import defaultdict
import heapq as hq
n,m,s = map(int,input().split())
edges = [[] for _ in range(n+1)]
INF = float('inf')
limit = 0
for i in range(m):
    u,v,a,b = map(int,input().split())
    edges[u].append((v,a,b))
    edges[v].append((u,a,b))
    limit += a
if s > limit:
    s = limit
exchanges = [0]
for i in range(n):
    c,d = map(int,input().split())
    exchanges.append((c,d))
dp = [[INF]*(limit+1) for _ in range(n+1)]
q = []
hq.heapify(q)
hq.heappush(q,(0,1,s))
dp[1][s] = 0
while q:
    time,place,silver = hq.heappop(q)
    c,d = exchanges[place]
    if silver + c <= limit:
        if time+d < dp[place][silver+c]:
            dp[place][silver+c] = time+d
            hq.heappush(q,(time+d,place,silver+c))
    else:
        if time+d < dp[place][limit]:
            dp[place][limit] = time+d
            hq.heappush(q,(time+d,place,limit))
    for v,a,b in edges[place]:
        if silver-a >= 0 and dp[v][silver-a] > time+b:
            dp[v][silver-a] = time+b
            hq.heappush(q,(time+b,v,silver-a))

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

Solution (Python):



import logging

handler = logging.FileHandler(filename="log")
handler.setFormatter(logging.Formatter('%(asctime)s %(levelname)8s %(message)s'))
logger = logging.getLogger(__name__)
logger.addHandler(handler)







from pprint import pprint as pp
from pprint import pformat as pf
import math


from heapq import heappush, heappop
class PriorityQueue:

    def __init__(self):
        self.contaier = []

    def push(self, time, city, money):
        heappush(self.contaier, (time, (city, money)))

    def pop(self):
        time, taple = heappop(self.contaier)
        return time, taple[0], taple[1]

    def is_empty(self):
        return len(self.contaier) == 0

class Data:

    def __init__(self, money, time):
        self.money = money
        self.time = time

    def __repr__(self):
        return "money {} time {}".format(self.money, self.time)


class Path:
    def __init__(self, frm, to):
        self.frm = frm
        self.to = to

def get_line_info(num_city, num_line):
    line_info = {}
    for i in range(num_city):
        line_info[i] = {}
    for i in range(num_line):
        frm, to, money, time = map(int, input().split())
        frm -= 1
        to -= 1
        line_info[frm][to] = Data(money, time)
        line_info[to][frm] = line_info[frm][to]
    return line_info

class Person:

    def __init__(self, num_city, city_info, line_info):
        
        
        
        
        self.city_info = city_info
        self.line_info = line_info
        self.que = PriorityQueue()
        self.dp = [None] * num_city 
        self.max_money = (50 * num_city)
        for i in range(num_city):
            self.dp[i] = [math.inf] * (self.max_money + 5)

    def travel(self, money):
        money = min(money, self.max_money)
        self.que.push(0, 0, money)
        while not self.que.is_empty():
            time, city, money = self.que.pop()
            
            
            self.exchange(time, city, money)
            self.walk_around(time, city, money)

    def exchange(self, time, city, money):
        time += self.city_info[city].time
        money += self.city_info[city].money
        self.save_and_push(time, city, money)

    def walk_around(self, time, city, money):
        for to in self.line_info[city]:
            self.walk(city, to, time, money)

    def walk(self, frm, to, time, money):
        time += self.line_info[frm][to].time
        money -= self.line_info[frm][to].money
        self.save_and_push(time, to, money)

    def save_and_push(self, time, city, money):
        if money < 0:
            return
        if not (money < len(self.dp[0])):
            return
        if time < self.dp[city][money]:
            self.dp[city][money] = time
            self.que.push(time, city, money)

    def print_ans(self):
        for city_dp in self.dp[1:]:
            print(min(city_dp))




if __name__ == '__main__':
    num_city, num_line, first_money = map(int, input().split())
    line_info = get_line_info(num_city, num_line)
    city_info = [None] * num_city
    for i in range(num_city):
        money, time = map(int, input().split())
        city_info[i] = Data(money, time)
    p = Person(num_city, city_info, line_info)
    p.travel(first_money)
    p.print_ans()

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

import heapq
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = {u: [] for u in range(n)}
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) 
ans = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)

    if ans[u][ss] is not None and ans[u][ss] <= dd:
        continue
    ans[u][ss] = dd
    
    
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or ans[v][ss-a[e]] is not None:
            continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    
    if ss+c[u] <= maxs:
        heapq.heappush(h, (dd + d[u], u, ss+c[u]))
    elif ss < maxs:
        heapq.heappush(h, (dd + d[u], u, maxs))

for item in ans[1:]:
    print(min(item))

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

import heapq
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = {u: set() for u in range(n)}
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) 
ans = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)

    if ans[u][ss] is not None and ans[u][ss] <= dd:
        continue
    ans[u][ss] = dd
    
    
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or ans[v][ss-a[e]] is not None:
            continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    
    if ss+c[u] <= maxs:
        heapq.heappush(h, (dd + d[u], u, ss+c[u]))
    elif ss < maxs:
        heapq.heappush(h, (dd + d[u], u, maxs))

for item in ans[1:]:
    print(min(item))

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

import heapq
from collections import defaultdict
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = defaultdict(set)
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) 
ans = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)

    if ans[u][ss] is not None and ans[u][ss] <= dd:
        continue
    ans[u][ss] = dd
    
    
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or ans[v][ss-a[e]] is not None:
            continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    
    if ss+c[u] <= maxs:
        heapq.heappush(h, (dd + d[u], u, ss+c[u]))
    elif ss < maxs:
        heapq.heappush(h, (dd + d[u], u, maxs))

for item in ans[1:]:
    print(min(item))

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

import heapq
from collections import defaultdict
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = defaultdict(list)
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) 
ans = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)

    if ans[u][ss] is not None and ans[u][ss] <= dd:
        continue
    ans[u][ss] = dd
    
    
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or ans[v][ss-a[e]] is not None:
            continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    
    if ss+c[u] <= maxs:
        heapq.heappush(h, (dd + d[u], u, ss+c[u]))
    elif ss < maxs:
        heapq.heappush(h, (dd + d[u], u, maxs))

for item in ans[1:]:
    print(min(item))

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

import heapq
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = {u: [] for u in range(n)}
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) 
ans = [[None] * (maxs+1) for _ in range(n)]
ans[0][s] = 0
done = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)



    
    if done[u][ss]:
        continue
    done[u][ss] = True
    
    
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or done[v][ss-a[e]] :
            continue
        ans[v][ss-a[e]] = min(ans[v][ss-a[e]], dd + b[e]) if ans[v][ss-a[e]] is not None else dd+b[e]


        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    
    if ss+c[u] <= maxs:
        sss = ss+c[u]
    elif ss < maxs:
        sss = maxs
    else:
        continue
    heapq.heappush(h, (dd + d[u], u, sss))

    ans[u][sss] = min(ans[u][sss], dd + d[u]) if ans[u][sss] is not None else dd+d[u]

for item in ans[1:]:
    print(min(item))

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

import heapq
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = {u: set() for u in range(n)}
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) 
ans = [[None] * (maxs+1) for _ in range(n)]
ans[0][s] = 0
done = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)



    
    if done[u][ss]:
        continue
    done[u][ss] = True
    
    
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or done[v][ss-a[e]] :
            continue
        ans[v][ss-a[e]] = min(ans[v][ss-a[e]], dd + b[e]) if ans[v][ss-a[e]] is not None else dd+b[e]


        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    
    if ss+c[u] <= maxs:
        sss = ss+c[u]
    elif ss < maxs:
        sss = maxs
    else:
        continue
    heapq.heappush(h, (dd + d[u], u, sss))

    ans[u][sss] = min(ans[u][sss], dd + d[u]) if ans[u][sss] is not None else dd+d[u]

for item in ans[1:]:
    print(min(item))

Solution (Python):

import sys
input = lambda : sys.stdin.readline().rstrip()

import heapq
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = {}
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns.setdefault(u-1, set())
    ns.setdefault(v-1, set())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) 
ans = [[None] * (maxs+1) for _ in range(n)]
ans[0][s] = 0
done = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)



    
    if done[u][ss]:
        continue
    done[u][ss] = True
    
    
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or done[v][ss-a[e]] :
            continue
        ans[v][ss-a[e]] = min(ans[v][ss-a[e]], dd + b[e]) if ans[v][ss-a[e]] is not None else dd+b[e]


        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    
    if ss+c[u] <= maxs:
        sss = ss+c[u]
    elif ss < maxs:
        sss = maxs
    else:
        continue
    heapq.heappush(h, (dd + d[u], u, sss))

    ans[u][sss] = min(ans[u][sss], dd + d[u]) if ans[u][sss] is not None else dd+d[u]

for item in ans[1:]:
    print(min(item))