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
input = sys.stdin.buffer.readline

def main():

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

    for i in range(n):
        c, d = map(int, input().split())
        for j in range(2501):
            k = j+c
            if 0 <= k <= 2500:
                g[i+n*j].append((d, i+n*k))

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

    s_ = 0+min(s, 2500)*n
    d = dijkstra_heap(s_, g, n*2501)
    
    for i in range(1, n):
        min_ = INF
        for j in range(2501):
            k = i+n*j
            min_ = min(min_, d[k])
        print(min_)

if __name__ == '__main__':
    main()

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

def main():

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

    for i in range(n):
        c, d = map(int, input().split())
        for j in range(2501):
            k = j+c
            if 0 <= k <= 2500:
                g[i+n*j].append((d, i+n*k))

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

    s_ = 0+min(s, 2500)*n
    d = dijkstra_heap(s_, g, n*2501)
    
    for i in range(1, n):
        min_ = INF
        for j in range(2501):
            k = i+n*j
            min_ = min(min_, d[k])
        print(min_)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.readline


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

d = defaultdict(list)
e = defaultdict(int)

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

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

dist = defaultdict(lambda :10**30)
ans = defaultdict(lambda :10**30)

source = (1, S)
dist[source] = 0
q = [(0, source)]

while q:
    cost, (s, nokori) = heappop(q)
    ns = (s, nokori)

    u, v = e[s]
    if dist[ns] < cost:
        continue

    if nokori > 2500:
        nokori = 2500
    else:
        n_nokori = nokori + u
        n_cost = v
        if n_nokori > 2500:
            n_nokori = 2500
        nt = (s, n_nokori)
        
        if dist[nt] > dist[ns]+n_cost:
            dist[nt] = dist[ns]+n_cost
            heappush(q, (dist[nt], nt))
    
    for a, b, t in d[s]:
        n_nokori = nokori - a
        n_cost = b
        
        nt = (t, n_nokori)

        if n_nokori < 0:
            continue
        if dist[nt] > dist[ns]+n_cost:
            dist[nt] = dist[ns]+n_cost
            heappush(q, (dist[nt], nt))

for (s, _), v in dist.items():
    ans[s] = min(ans[s], v)

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

Solution (Python):
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7


    n, m, s = map(int, input().split())
    s = min(s, 2500)
    from collections import defaultdict
    
    import heapq
    def dijkstra(s, x):
        
        d = defaultdict(lambda: float("inf"))
        d[(s, x)] = 0
        
        used = defaultdict(lambda: False)
        used[(s, x)] = True
        
        que = []
        for e in edge[(s, x)]:
            heapq.heappush(que, e)
        while que:
            minedge = heapq.heappop(que)
            if used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = True
            for e in edge[v]:
                if not used[e[1]]:
                    heapq.heappush(que, (e[0] + d[v], e[1]))
        return d

    max_money = 2500
    edge = defaultdict(list)
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        for i in range(a, max_money + 1):
            edge[(u, i)].append((b, (v, i - a)))
            edge[(v, i)].append((b, (u, i - a)))
    for j in range(n):
        c, d = map(int, input().split())
        for i in range(max_money):
            if i + c <= max_money:
                edge[(j, i)].append((d, (j, i + c)))

    ans = [10**18]*n

    d = dijkstra(0, s)
    for i in d:
        x, y = i
        cost = d[i]
        ans[x] = min(ans[x], cost)
    for i in ans[1:]:
        print(i)
main()

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

    n, m, s = map(int, input().split())
    s = min(s, 2500)
    from collections import defaultdict
    
    import heapq
    def dijkstra(s, x):
        
        d = defaultdict(lambda: float("inf"))
        d[(s, x)] = 0
        
        used = defaultdict(lambda: False)
        used[(s, x)] = True
        
        que = []
        for e in edge[(s, x)]:
            heapq.heappush(que, e)
        while que:
            minedge = heapq.heappop(que)
            if used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = True
            for e in edge[v]:
                if not used[e[1]]:
                    heapq.heappush(que, (e[0] + d[v], e[1]))
        return d

    max_money = 2500
    edge = defaultdict(list)
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        for i in range(a, max_money + 1):
            edge[(u, i)].append((b, (v, i - a)))
            edge[(v, i)].append((b, (u, i - a)))
    for j in range(n):
        c, d = map(int, input().split())
        for i in range(max_money):
            if i + c <= max_money:
                edge[(j, i)].append((d, (j, i + c)))

    ans = [10**18]*n

    d = dijkstra(0, s)
    for i in d:
        x, y = i
        cost = d[i]
        ans[x] = min(ans[x], cost)
    for i in ans[1:]:
        print(i)
main()

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

n, m, s = map(int, input().split())
s = min(s, 2500)
from collections import defaultdict

import heapq
def dijkstra(s, x):
    
    d = defaultdict(lambda: float("inf"))
    d[(s, x)] = 0
    
    used = defaultdict(lambda: False)
    used[(s, x)] = True
    
    que = []
    for e in edge[(s, x)]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, (e[0] + d[v], e[1]))
    return d

max_money = 2500
edge = defaultdict(list)
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for i in range(a, max_money + 1):
        edge[(u, i)].append((b, (v, i - a)))
        edge[(v, i)].append((b, (u, i - a)))
for j in range(n):
    c, d = map(int, input().split())
    for i in range(max_money):
        if i + c <= max_money:
            edge[(j, i)].append((d, (j, i + c)))

ans = [10**18]*n

d = dijkstra(0, s)
for i in d:
    x, y = i
    cost = d[i]
    ans[x] = min(ans[x], cost)
for i in ans[1:]:
    print(i)

Solution (Python):

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from heapq import heappush, heappop

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

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

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

    hq = [(0, 0, S)]
    INF = 10**18
    
    
    dp = [[INF]*2501 for _ in range(N)]
    dp[0][S] = 0

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

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

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

main()

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

def main():
    N,M,S = map(int,input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        edge[u-1].append((v-1, a, b))
        edge[v-1].append((u-1, a, b))
    
    change = [tuple(map(int,input().split())) for _ in range(N)]
    MAX_COST = 50*50
    S = min(S, MAX_COST)
    
    q = [(0,(0,S))]
    ans = [-1]*N
    visited = set()
    heapq.heapify(q)
    
    while q:
        time, data = heapq.heappop(q)
        now, money = data
        if ans[now] == -1:
            ans[now] = time
            if -1 not in ans:
                break
        if data in visited:
            continue
        visited.add(data)
        for fol, a, b in edge[now]:
            if money >= a:
                fol_data = (fol, money-a)
                if fol_data in visited:
                    continue
                heapq.heappush(q, (time+b, fol_data))
        c, d = change[now]
        if money+c > MAX_COST:
            continue
        heapq.heappush(q, (time+d, (now, money+c)))
    
    print(*ans[1:], sep="\n")

if __name__ == "__main__":
    main()

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

def main():
    N,M,S = map(int,input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        edge[u-1].append((v-1, a, b))
        edge[v-1].append((u-1, a, b))
    
    change = [tuple(map(int,input().split())) for _ in range(N)]
    MAX_COST = 50*50
    S = min(S, MAX_COST)
    
    q = [(0,(0,S))]
    ans = [-1]*N
    visited = set()
    heapq.heapify(q)
    
    while q:
        time, data = heapq.heappop(q)
        now, money = data
        if ans[now] == -1:
            ans[now] = time
            if -1 not in ans:
                break
        if data in visited:
            continue
        visited.add(data)
        for fol, a, b in edge[now]:
            if money >= a:
                fol_data = (fol, money-a)
                if fol_data in visited:
                    continue
                heapq.heappush(q, (time+b, fol_data))
        c, d = change[now]
        if money+c > MAX_COST:
            continue
        heapq.heappush(q, (time+d, (now, money+c)))
    
    print(*ans[1:], sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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

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

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

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

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

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

Solution (Python):

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

MAX_SILVER = 3000 

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

n, m, s = map(int, input().split())
edge = [[] for _ in range(n * MAX_SILVER)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1; v -= 1
    for i in range(a, MAX_SILVER):
        edge[u*MAX_SILVER + i].append((v*MAX_SILVER + i-a, b))
        edge[v*MAX_SILVER + i].append((u*MAX_SILVER + i-a, b))

for v in range(n):
    c, d = map(int, input().split())
    for i in range(MAX_SILVER - 100):
        edge[v*MAX_SILVER + i].append((v*MAX_SILVER + i + c, d))

DIJK = Dijkstra(edge)
if s > 2500:
    s = 2500
dist = DIJK.calc(s)

for v in range(1, n): 
    ret = INF
    for val in range(MAX_SILVER):
        if dist[v*MAX_SILVER + val] < ret:
            ret = dist[v*MAX_SILVER + val]
    print(ret)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m,s = map(int,ipt().split())
    mac = 2500
    way = [[] for i in range(n+1)] 
    for _ in range(m):
        u,v,a,b = map(int,ipt().split())
        way[u].append((v,a,b))
        way[v].append((u,a,b))
    for i in range(1,n+1):
        c,d = map(int,ipt().split())
        way[i].append((i,-c,d))
    ct = [[10**18]*2501 for i in range(n+1)]
    ct[1][min(s,mac)] = 0 
    hq = [(0,1,min(s,mac))] 
    while hq:
        ti,pl,mo = hpq.heappop(hq)
        for dp,dm,dt in way[pl]:
            if mo >= dm and ct[dp][min(mo-dm,mac)] > ti+dt:
                 ct[dp][min(mo-dm,mac)] = ti+dt
                 hpq.heappush(hq,(ti+dt,dp,min(mo-dm,mac)))
    ans = [min(i) for i in ct[2::]]
    for i in ans:
        print(i)
    return

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop, heappush
n, m, s = map(int, input().split())
edges = [[[] for _ in range(2501)] for _ in range(n)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for x in range(2501):
        if x - a >= 0:
            edges[u-1][x].append((b, v-1, x-a))
            edges[v-1][x].append((b, u-1, x-a))

for i in range(n):
    c, d = map(int, input().split())
    for x in range(2500):
        edges[i][x].append((d, i, min(2500, x+c)))

inf = 1e15
d = [[inf for _ in range(2501)] for _ in range(n)]
s = min(s, 2500)
def dijkstra():
    que = []
    d[0][s] = 0
    heappush(que, (0, 0, s))

    while len(que):
        dist, city, coins = heappop(que)

        if d[city][coins] < dist:
            continue
        for cost, to_city, to_coins in edges[city][coins]:
            if d[to_city][to_coins] > dist + cost:
                d[to_city][to_coins] = dist + cost
                heappush(que, (d[to_city][to_coins], to_city, to_coins))


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

Solution (Python):
import heapq
n,m,s = map(int,input().split())
lst_graph = [list(map(int,input().split())) for _ in range(m)]
lst_cd = [list(map(int,input().split())) for _ in range(n)]
graph = [[] for _ in range(2501*n)]


def f(x,c):
    if c >= 2500:
        c = 2500
    return (x-1)*2501+c



for i in range(m):
    u,v,a,b = lst_graph[i]
    for c in range(2501):
        if c >= a:
            graph[f(u,c)].append((b,f(v,c-a)))
            graph[f(v,c)].append((b,f(u,c-a)))
for i in range(1,n+1):
    x,time = lst_cd[i-1]
    for c in range(2500):
        graph[f(i,c)].append((time, f(i,c+x)))



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

ans = dijkstra_heap(f(1,s),graph)
for i in range(1,n):
    print(min(ans[(2501*i):(2501*i+2501)]))

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

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


N, M, S = lr()
limit = 2500
S = min(S, limit)
graph = [[] for _ in range((N+1) * (limit+1))]  
for _ in range(M):
    u, v, a, b = lr()
    for x in range(a, limit+1):
        graph[u*(limit+1) + x].append(((v*(limit+1)+x-a), b))
        graph[v*(limit+1) + x].append(((u*(limit+1)+x-a), b))

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

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

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

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

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


N, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a

limit = Amax*(N-1)
S = min(S, limit)
graph = [[] for _ in range(N+1)] 
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start):
    
    INF = 10 ** 15
    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev-1]
        si = min(limit, silver+c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time+d, si, prev))
            si += c; si = min(limit, si)
            time += d
            
    return dist

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

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

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


N, M, S = lr()
limit = 2500
S = min(S, limit)
graph = [[] for _ in range((N+1) * (limit+1))]  
for _ in range(M):
    u, v, a, b = lr()
    for x in range(a, limit+1):
        graph[u*(limit+1) + x].append(((v*(limit+1)+x-a), b))
        graph[v*(limit+1) + x].append(((u*(limit+1)+x-a), b))

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

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

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

Solution (Python):
import heapq as hq
N,M,S = list(map(int, input().split()))

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


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

MAXYEN = 50 * N
dp = [[ 1e18 for i in range(MAXYEN + 5) ] for _ in range(N)]
S = min(MAXYEN, S)
dp[0][S] = 0


Q = []
hq.heapify(Q)
hq.heappush(Q, [0,0,S])

while len(Q) > 0:
  nowt, nowi, nowm = hq.heappop(Q)
  
  
  for e in E[nowi]:
    to_i, costm, costt = e
    
    if nowm - costm < 0:
      
      continue
    if dp[to_i][nowm-costm] > dp[nowi][nowm] + costt:
      dp[to_i][nowm-costm] = dp[nowi][nowm] + costt
      hq.heappush(Q, [dp[nowi][nowm] + costt, to_i, nowm-costm])
      
  
  getm, costt = C[nowi]
  targetm = min(MAXYEN, nowm + getm)
  
  if dp[nowi][targetm] > dp[nowi][nowm] + costt:
    dp[nowi][targetm] = dp[nowi][nowm] + costt
    hq.heappush(Q, [dp[nowi][targetm], nowi, targetm])
  
for i in range(1,N):
  print(min(dp[i]))

Solution (Python):
import heapq as hq
N,M,S = list(map(int, input().split()))

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


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

MAXYEN = 50 * N
dp = [[ 1e18 for i in range(MAXYEN + 5) ] for _ in range(N)]
S = min(MAXYEN, S)
dp[0][S] = 0


Q = []
hq.heapify(Q)
hq.heappush(Q, [0,0,S])

while len(Q) > 0:
  nowt, nowi, nowm = hq.heappop(Q)
  
  
  for e in E[nowi]:
    to_i, costm, costt = e
    
    if nowm - costm < 0:
      
      continue
    if dp[to_i][nowm-costm] > dp[nowi][nowm] + costt:
      dp[to_i][nowm-costm] = dp[nowi][nowm] + costt
      hq.heappush(Q, [dp[nowi][nowm] + costt, to_i, nowm-costm])
      
  
  getm, costt = C[nowi]
  targetm = min(MAXYEN, nowm + getm)
  
  if dp[nowi][targetm] > dp[nowi][nowm] + costt:
    dp[nowi][targetm] = dp[nowi][nowm] + costt
    hq.heappush(Q, [dp[nowi][targetm], nowi, targetm])
  
for i in range(1,N):
  print(min(dp[i]))

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math


MOD = 998244353


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

G = [[] for _ in range(N)]
for i in range(M):
    u, v, s, t = map(int, input().split())
    G[u-1].append([v-1, s, t])
    G[v-1].append([u-1, s, t])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    change_rate.append(rate)
    change_cost.append(cost)


dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][S] = 0


pq = [(0, 0, S)]
while pq:
    time, node, silver = heapq.heappop(pq)

    
    next_silver = min(silver + change_rate[node], MAX_COST)
    next_time = time + change_cost[node]
    if next_time < dp[node][next_silver]:
        dp[node][next_silver] = next_time
        heapq.heappush(pq, (next_time, node, next_silver))

    for nei, ns, nt in G[node]:
        remain_silver = min(silver - ns, MAX_COST)
        next_time = time + nt
        if remain_silver >= 0 and next_time < dp[nei][remain_silver]:
            dp[nei][remain_silver] = next_time
            heapq.heappush(pq, (next_time, nei, remain_silver))

for d in dp[1:]:
    print(min(d))