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
import heapq

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

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

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

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

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

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

queue = []


def dijakstra(q):
    while q != []:
        hwd = heapq.heappop(q)

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

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

ans = dijakstra(queue)

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

Solution (Python):
import math

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

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

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

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

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

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


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

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

queue = []


def dijakstra(q):
    while q != []:
        hwd = q.pop(0)

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

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

ans = dijakstra(queue)

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

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

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


def main():

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

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


if __name__ == '__main__':
    main()

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

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


def main():

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import collections


def main():
    INF = 10 ** 15
    
    N, M, S = list(map(int, input().split()))
    SUM_A = 0
    A = [[INF for _ in range(N)] for _ in range(N)]  
    B = [[INF for _ in range(N)] for _ in range(N)]  
    C = [0 for _ in range(N)]  
    D = [0 for _ in range(N)]  
    ADJ = collections.defaultdict(list)
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        A[u][v] = a
        A[v][u] = a
        B[u][v] = b
        B[v][u] = b
        ADJ[u].append(v)
        ADJ[v].append(u)
        SUM_A += a
    S = min(SUM_A, S)  
    for n in range(N):
        c, d = list(map(int, input().split()))
        C[n] = c
        D[n] = d
    
    
    arr_dist = [[INF for _ in range(SUM_A + 1)] for _ in range(N)]
    arr_dist[0][S] = 0
    que = [(0, 0, S)]  
    while len(que) > 0:
        dist, city, silver = heapq.heappop(que)
        
        next_silver, next_dist = silver + C[city], dist + D[city]
        if next_silver <= SUM_A and arr_dist[city][next_silver] > next_dist:
            arr_dist[city][next_silver] = next_dist
            heapq.heappush(que, (next_dist, city, next_silver))
        
        for next_city in ADJ[city]:
            next_silver, next_dist = silver - A[city][next_city], dist + B[city][next_city]
            if 0 <= next_silver <= SUM_A and arr_dist[next_city][next_silver] > next_dist:
                arr_dist[next_city][next_silver] = next_dist
                heapq.heappush(que, (next_dist, next_city, next_silver))
    
    min_dist = [0 for _ in range(N)]
    for city in range(1, N):
        min_dist[city] = min(arr_dist[city])
    for ans in min_dist[1:]:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from heapq import heappop, heappush

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

lim = 2501
graph = [[] for _ in range((N + 1) * lim)]

for u, v, a, b in X:
    for n in range(a, lim):
        graph[u * lim + n].append((v * lim + (n - a), b))
        graph[v * lim + n].append((u * lim + (n - a), b))

for n, (c, d) in enumerate(Y):
    for x in range(lim - 1):
        graph[(n + 1) * lim + x].append(
            ((n + 1) * lim + min(lim - 1, x + c), d))


INF = 10 ** 20
start = lim + min(S, lim - 1)
dist = [INF] * ((N + 1) * lim + 1)
dist[start] = 0
pq = []
heappush(pq, (0, start))

while pq:
    _, u = heappop(pq)
    for v, c in graph[u]:
        if dist[v] > dist[u] + c:
            dist[v] = dist[u] + c
            heappush(pq, (dist[v], v))

ans = []
for i in range(2, N + 1):
    ans.append(min(dist[i * lim:i * lim + lim]))

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

Solution (Python):
N,M,S=map(int,input().split())
UVAB=[list(map(int,input().split())) for i in range(M)]
C,D=zip(*[list(map(int,input().split())) for i in range(N)])
c=[[] for i in range(N)]
A=[[] for i in range(N)]
B=[[] for i in range(N)]
for u,v,a,b in UVAB:
    c[u-1].append(v-1)
    c[v-1].append(u-1)
    A[u-1].append(a)
    A[v-1].append(a)
    B[u-1].append(b)
    B[v-1].append(b)
inf=10**20
from heapq import heappop,heappush
X=50*(N-1)
def dij(p,s):
    d=[[inf]*(X+1) for i in range(N)]
    d[p][s]=0
    q=[]
    heappush(q,(0,(p,s)))
    while q:
        t,(p,s)=heappop(q)
        for i in range(1,(X+1-s)//C[p]):
            if X<s+i*C[p] or d[p][s+i*C[p]]<=d[p][s]+i*D[p]:break
            d[p][s+i*C[p]]=d[p][s]+i*D[p]
            heappush(q,(d[p][s]+i*D[p],(p,s+i*C[p])))
        for j,n in enumerate(c[p]):
            if 0<=s-A[p][j] and d[n][s-A[p][j]]>d[p][s]+B[p][j]:
                d[n][s-A[p][j]]=d[p][s]+B[p][j]
                heappush(q,(d[n][s-A[p][j]],(n,s-A[p][j])))
    return d
d=dij(0,min(S,X))
print(*[min(x) for x in d[1:]],sep='\n')

Solution (Python):
import heapq


UNVISITED = -1

def construct_incidence_list(tail, head):
    n=2500*N
    m=len(head)

    edge_first = [0] * n
    edge_next = [0] * m

    for i in range(m, 0, -1):
        v = tail[i-1]
        edge_next[i-1] = edge_first[v-1]
        edge_first[v-1] = i

    return edge_first, edge_next


def main():
    tail=[]
    head=[]
    length=[]
    for i in range(M):
      u,v,a,b=map(int,input().split())
      for j in range(2499,a-1,-1):
        tail.append(2500*(u-1)+j)
        head.append(2500*(v-1)+j-a)
        length.append(b)
        head.append(2500*(u-1)+j-a)
        tail.append(2500*(v-1)+j)
        length.append(b)
    for i in range(N):
      c,d=map(int,input().split())
      for j in range(2499):
        tail.append(2500*(i)+j)
        head.append(2500*(i)+min(j+c,2499))
        length.append(d)

    start = min(S,2499)

    edge_first, edge_next = construct_incidence_list(tail, head)
    
    n = 2500*N
    distance = [0] * (n+1)
    path = [0] + [UNVISITED for v in range(1, n+1)]
    distance[start] = 0
    path[start] = 0
    hq = [(0, start)]
    heapq.heapify(hq)

    while len(hq) > 0:
        _, v1 = heapq.heappop(hq)

        edge_to_v2 = edge_first[v1-1]
        while edge_to_v2 != 0:
            v2 = head[edge_to_v2-1]
            dist_candidate = distance[v1] + length[edge_to_v2-1]
            if path[v2] == UNVISITED or distance[v2] > dist_candidate:
                distance[v2] = dist_candidate
                path[v2] = edge_to_v2
                heapq.heappush(hq, (distance[v2], v2))

            edge_to_v2 = edge_next[edge_to_v2-1]

    for i in range(1,N):
      ans=10**18
      for j in range(2500):
        if distance[i*2500+j]==0:
          continue
        if distance[i*2500+j]<ans:
          ans=distance[i*2500+j]
      print(ans)
    


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

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, M, S = LI()
    UVAB = LIR(M)
    CD = LIR(N)

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

    dist = [[INF] * 2500 for _ in range(N)]
    heap = [(0, 0, min(2500, S))]

    while heap:
        cost, u, s = heappop(heap)
        c, d = CD[u]

        if s + c < 2500 and dist[u][s + c] > cost + d:
            dist[u][s + c] = cost + d
            heappush(heap, (cost + d, u, s + c))
        for v, a, b in edge[u]:
            if s - a >= 0 and dist[v][s - a] > cost + b:
                dist[v][s - a] = cost + b
                heappush(heap, (cost + b, v, s - a))

        

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

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**18
U = N*50
S = min(S, U)
dist = [[inf] * (U + 1) for _ in range(N)]
dist[0][S] = 0

que = [(0, -S, 0)]  
while que:
    time, silver, now = heapq.heappop(que)
    silver = -silver
    if dist[now][silver] < time:
        continue
    
    c, d = CD[now]
    n = 1
    while silver + c * n <= U:
        if dist[now][silver + c * n] > time + n * d:
            dist[now][silver + c * n] = time + n * d
            heapq.heappush(que, (time + n * d, -(silver + c * n), now))
            n += 1
        else:
            break
    
    for nxt, s, t in edge[now]:
        if silver < s:
            continue
        if dist[nxt][silver - s] > time + t:
            dist[nxt][silver - s] = time + t
            heapq.heappush(que, (time + t, -(silver - s), nxt))

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

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

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

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

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

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

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

Solution (Python):
import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) 
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  
  
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) 
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) 
  while len(edgelist):
    
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

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

Solution (Python):
import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) 
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  
  
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) 
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) 
  while len(edgelist):
    
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

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

Solution (Python):
import heapq

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

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

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

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

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())
    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 sys
from heapq import *
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

@njit((i8, i8, i8[:, :], i8[:]), cache=True)
def main(N, S, G, CD):
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')
    U = 2600
    C, D = CD[::2], CD[1::2]
    C = np.minimum(C, U)
    S = np.minimum(S, U)
    INF = 10**18
    dist = np.full((N + 1, U + 1), INF, np.int64)
    dist[1, S] = 0
    q = [(0, 1, S)]
    while q:
        d, v, coin = heappop(q)
        if dist[v, coin] < d:
            continue
        for i in range(ind[v - 1], ind[v]):
            w, a, b = G[i, 1:]
            if coin < a:
                continue
            if dist[w, coin - a] <= d + b:
                continue
            dist[w, coin - a] = d + b
            heappush(q, (d + b, w, coin - a))
        c = min(U, coin + C[v - 1])
        if dist[v, c] <= d + D[v - 1]:
            continue
        dist[v, c] = d + D[v - 1]
        heappush(q, (d + D[v - 1], v, c))
    return dist

N, M, S = map(int, readline().split())
nums = np.array(read().split(), np.int64)
UVAB = nums[:4 * M]
CD = nums[4 * M:]

U, V, A, B = UVAB.reshape(-1, 4).T

G = np.empty((M + M, 4), np.int64)
G[:, 0] = np.concatenate((U, V))
G[:, 1] = np.concatenate((V, U))
G[:, 2] = np.concatenate((A, A))
G[:, 3] = np.concatenate((B, B))
G = G[G[:, 0].argsort()]

ans = main(N, S, G, CD)[2:].min(axis=1)
print('\n'.join(map(str, ans.tolist())))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m,s = list(map(int, input().split()))
cd = [None]*n
from collections import defaultdict
ns = defaultdict(set)
nns = defaultdict(set)
uvab = [None]*m
for i in range(m):
    u,v,a,b = list(map(int, input().split()))
    u -= 1
    v -= 1
    uvab[i] = (u,v,a,b)
    ns[u].add((a,b,v))
    ns[v].add((a,b,u))
for i in range(n):
    cd[i] = list(map(int, input().split()))

ms = max(item[2] for item in uvab)*(n-1)
for u in range(n):
    for ss in range(ms+1):
        for a,b,v in ns[u]:
            if ss>=a:
                nns[u,ss].add((b, (v,ss-a)))
        c,d = cd[u]
        if ss+c<=ms:
            nns[u,ss].add((d, (u,ss+c)))
ns = nns
def dijkstra(start):
    import heapq
    vals = {}
    h = [(0, start)] 
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if v not in vals or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
s = min(s, ms)
vals = dijkstra((0,s))
ans = [None]*(n-1)
for u in range(1,n):
    ans[u-1] = min(vals[u,s] for s in range(ms+1))
write("\n".join(map(str, ans)))

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

ways=[[] for _ in range(N)]
CD=[[0]*2 for _ in range(N)]

class Way:
  def __init__(self,t,f,ti):
    self.to=t
    self.fare=f
    self.time=ti 

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

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

dp=[[float("inf")]*(50*N+1) for _ in range(N)]
S=min(S,50*N)
dp[0][S]=0
import heapq




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

def Push(time,station,money):
  
  global q,dp
  if money<0:
    return
  money=min(money,50*N)
  if dp[station][money] <= time:
    return
  dp[station][money] = time
  heapq.heappush(q,(time,station,money))

while q:
  
  dat = heapq.heappop(q)
  time,station,money=dat[0],dat[1],dat[2]
  
  if dp[station][money]!=time:
    continue
  
  Push(time+CD[station][1],station,money+CD[station][0])
  
  for w in ways[station]:
    Push(time+w.time,w.to,money-w.fare)

for i in range(1,N):
  ans=float("inf")
  for j in range(50*N+1):
    ans=min(ans,dp[i][j])
  print(ans)