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):
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


def idx(node, silver):
    silver = min(silver, SILVER_MAX)
    return node * (SILVER_MAX + 1) + silver


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

A_MAX = 50
SILVER_MAX = A_MAX * (n - 1)
N = (SILVER_MAX + 1) * n

U = []
V = []
C = []


for u, v, a, b in uvab:
    u -= 1
    v -= 1
    for silver in range(SILVER_MAX + 1):
        U.append(idx(u, silver + a))
        V.append(idx(v, silver))
        C.append(b)

        U.append(idx(v, silver + a))
        V.append(idx(u, silver))
        C.append(b)


for node, (c, d) in enumerate(cd):
    for silver in range(SILVER_MAX + 1):
        U.append(idx(node, silver))
        V.append(idx(node, silver + c))
        C.append(d)


for node in range(n):
    for silver in range(SILVER_MAX):
        U.append(idx(node, silver + 1))
        V.append(idx(node, silver))
        C.append(0)

g = csr_matrix((C, (U, V)), shape=(N, N))
start = idx(0, s)
dist = dijkstra(g, indices=start).astype(int)
ans = dist[idx(1, 0)::SILVER_MAX+1]
print(*ans, sep="\n")

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

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

for i in range(m):
    for j in range(2):
        A[i][j] -= 1

ma = max([A[i][2] for i in range(m)])
mc = ma * n + 3
vv = n * mc
M = [[] for i in range(vv)]



for i in range(n):
    for j in range(mc-1):
        p0 = i * mc + j
        p1 = i * mc + min(mc-1, j+C[i][0])
        d = C[i][1]
        M[p0].append([p1, d])



for i in range(n):
    for j in range(1, mc):
        p0 = i * mc + j
        p1 = i * mc + j-1
        d = 0
        M[p0].append([p1, d])





for i in range(m):
    for j in range(mc):
        p0 = A[i][0] * mc + j
        p1 = A[i][1] * mc + j-A[i][2]
        d = A[i][3]
        if j-A[i][2] >= 0:
            M[p0].append([p1, d])

        p0 = A[i][1] * mc + j
        p1 = A[i][0] * mc + j-A[i][2]
        d = A[i][3]
        if j-A[i][2] >= 0:
            M[p0].append([p1, d])



import heapq

st = min(s, mc-1)
nn = n
n = len(M)
D = [float("inf")] * n  

D[st] = 0
V = [0] * n  
Q = []  
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    
                    heapq.heappush(Q, [alt, v])



for i in range(1, nn):
    print(min(D[i*mc : (i+1)*mc]))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    n, m, s = map(int,input().split())
    S = 0
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int,input().split()) 
        u -= 1; v -= 1
        S += a
        E[u].append((v, -a, b))
        E[v].append((u, -a, b))
    for v in range(n):
        c, d = map(int,input().split())
        E[v].append((v, c, d))

    
    dist = [[INF] * (S + 1) for _ in range(n)]
    s = min(s, S)
    dist[0][s] = 0
    heap = [(0, 0, s)] 
    while heap:
        d, v, s = heappop(heap)
        if dist[v][s] < d:
            continue
        for nv, ds, dd in E[v]:
            ns = s + ds
            if not (0 <= ns <= S):
                continue
            if dist[nv][ns] > dist[v][s] + dd:
                dist[nv][ns] = dist[v][s] + dd
                heappush(heap, (dist[nv][ns], nv, ns))

    
    for v in range(1, n):
        print(min(dist[v][s] for s in range(S + 1)))
resolve()

Solution (Python):
import sys
import heapq

input = sys.stdin.readline

NCOSTS = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
adj = [[] for _ in range(N * NCOSTS)]
fare_adj = [[NCOSTS] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0


def node(city, silvers):
    return silvers * N + city


for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for j in range(a, NCOSTS):
        adj[node(u, j)].append((node(v, j - a), b))
        adj[node(v, j)].append((node(u, j - a), b))

for i in range(N):
    
    c, d = map(int, input().split())
    for j in range(NCOSTS - c):
        adj[node(i, j)].append((node(i, j + c), d))


mintime = [TIME_MAX for _ in range(N * NCOSTS)]


def search():
    q = [(0, node(0, min(S, NCOSTS - 1)))]
    while q:
        t, node1 = heapq.heappop(q)
        if t > mintime[node1]:
            continue
        for node2, cost in adj[node1]:
            ntime = t + cost
            if mintime[node2] > ntime:
                mintime[node2] = ntime
                heapq.heappush(q, (ntime, node2))


search()
for i in range(1, N):
    print(min(mintime[node(i, j)] for j in range(NCOSTS)))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = [None] * m
    S = 0
    for i in range(m):
        u, v, a, b = map(int,input().split())
        S += a
        E[i] = (u - 1, v - 1, -a, b)

    exchange = [tuple(map(int,input().split())) for _ in range(n)]
    dp = [[INF] * (S + 1) for _ in range(n)]
    dp[0][min(s, S)] = 0

    for _ in range(2 * n - 3):
        
        for v in range(n):
            for s in range(S + 1):
                ds, dt = exchange[v]
                dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt)
        
        for u, v, ds, dt in E:
            for s in range(S + 1):
                ns = s + ds
                if ns < 0:
                    continue
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)

    for v in range(1, n):
        print(min(dp[v][j] for j in range(S + 1)))
resolve()

Solution (Python):
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, 2500)

edges = [[] for _ in range(51 * 2501 + 1)]


for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 2501):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))


for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    
    for i in range(2501):
        
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)

ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])

print(*ans[2 : (n + 1)], sep="\n")

Solution (Python):
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, 2500)

edges = [[] for _ in range(51 * 2501 + 1)]


for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 2501):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))


for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    
    for i in range(2501):
        
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)

ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])

print(*ans[2 : (n + 1)], sep="\n")

Solution (Python):
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, 2500)

edges = [[] for _ in range(51 * 2501 + 1)]


for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 2501):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))


for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    
    for i in range(2501):
        
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)

ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])

print(*ans[2 : (n + 1)], sep="\n")

Solution (Python):
def dijkstra(v, G):
    import heapq

    ret = [10 ** 20] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


N, M, S = map(int, input().split())
UVAB = [tuple(map(int, input().split())) for _ in range(M)]
CD = [tuple(map(int, input().split())) for _ in range(N)]

maxA = max([a for u, v, a, b in UVAB])
Q = maxA * (N - 1) + 1
G = [[] for _ in range(Q * N)]

for u, v, a, b in UVAB:
    for q in range(Q):
        if q >= a:
            G[Q * (u - 1) + q].append((Q * (v - 1) + q - a, b))
            G[Q * (v - 1) + q].append((Q * (u - 1) + q - a, b))

for n, (c, d) in enumerate(CD):
    for q in range(Q):
        G[Q * n + q].append((Q * n + min(Q - 1, c + q), d))

ans = dijkstra(min(S, Q - 1), G)
for n in range(1, N):
    print(min(ans[Q * n:Q * (n + 1)]))

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]


m = 50*n+1

dp = [[-1]*m for _ in range(n)]


from heapq import heappush,heappop
h = []

for g in range(min(s+1,m+3)):
    heappush(h, (0,-g,0))

while len(h) > 0:
    t,g,i = h[0]
    g = -g

    

    heappop(h)
    if dp[i][min(g,m-1)] != -1:
        continue

    
    dp[i][min(g,m-1)] = t
    
    for v,a,b in edges[i]:
        if g-a >= 0 and dp[v][min(g-a,m-1)] == -1:
            heappush(h,(t+b,-(g-a),v))


    c,d = cd[i]
    heappush(h,(t+d,-(g+c),i))
    


for d in dp:
    pass



for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t


        if res == -1 or res > min_t+b:
            res = min_t+b


    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            continue
            res = t
            
    print(res)

Solution (Python):
import collections
import heapq


class Dijkstra:
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

N,M,S = map(int,input().split())
train = [list(map(int,input().split())) for i in range(M)]
change = [list(map(int,input().split())) for i in range(N)]

if S > 2500:
    S = 2500

G = Dijkstra()

for u,v,a,b in train:
    for i in range(a,2501):
        G.e[(u,i)].append([(v,i-a),b])
        G.e[(v,i)].append([(u,i-a),b])
for i in range(1,N+1):
    for j in range(2501-change[i-1][0]):
        G.e[(i,j)].append([(i,j+change[i-1][0]),change[i-1][1]])

A = G.search((1,S))

for i in range(2,N+1):
    print(min(A[(i,j)] for j in range(2501)))

Solution (Python):
import sys
import math
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush
import numpy as np
from array import array




MAX_INT = 2**62-1
MOD = 10**9 + 7


if __name__ == "__main__":
    n, m, s = map(int, input().split())
    cost = {}
    time = {}
    g = defaultdict(list)

    for _ in range(m):
        u, v, a, b = map(int, input().split())
        cost[u, v] = cost[v, u] = a
        time[u, v] = time[v, u] = b
        g[u].append(v)
        g[v].append(u)

    for i in range(1, n+1):
        c, d = map(int, input().split())
        cost[i, i] = -c
        time[i, i] = d
        g[i].append(i)

    max_money = n * 50
    s = min(max_money, s)
    pq = [(0, 1, s)]
    time_usage = [[float('inf')] * (max_money+1) for _ in range(n+1)]
    time_usage[1][s] = 0

    while pq:
        t, cur, money = heappop(pq)
        if t > time_usage[cur][money]:
            continue
        for nxt in g[cur]:
            nt = t + time[cur, nxt]
            nm = min(money - cost[cur, nxt], max_money)
            if nm >= 0 and nt < time_usage[nxt][nm]:
                time_usage[nxt][nm] = nt
                heappush(pq, (nt, nxt, nm))

    for ts in time_usage[2:]:
        print(min(ts))

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


import heapq
n,m,s = inm()
ST = 51*(n+1)
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
s = min(s,ST-1)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

dst2 = [[] for i in range((n+1)*ST)]
for u in range(1,n+1):
    for p in range(ST-c[u]):
        dst2[u*ST+p].append((u*ST+p+c[u], d[u]))
    for v in dst[u]:
        m = dst[u][v][0]
        t = dst[u][v][1]
        for p in range(m,ST):
            dst2[u*ST+p].append((v*ST+p-m,t))

if DBG:
    print("dst2)")
    for u,p in [(1,50),(2,50),(1,3)]:
        
        ddprint("u {u} p {p} d2 {dst2[u*ST+p]}")
        for z in dst2[u*ST+p]:
            ddprint("v {z[0]//ST} q {z[0]%ST} t {z[1]}")

cost = [BIG]*((n+1)*ST)
q = [(0,1*ST+s)]
while len(q)>0:
    dd,u = heapq.heappop(q)
    if cost[u]<=dd:
        continue
    cost[u] = dd
    for v,t in dst2[u]:
        heapq.heappush(q,(dd+t, v))

if DBG:
    print("cost) ST {ST} s {s}")
    for u,p in [(2,204),(3,154),(4,154)]:
        ddprint("u {u} p {p} suf {u*ST+p} cost {cost[u*ST+p]}")

ddprint(cost)
ans = [BIG]*(n+1)
for i in range(2,n+1):
    ans[i] = min(cost[i*ST:(i+1)*ST])
    
    ddprint(cost[i*ST:(i+1)*ST])
for i in range(2,n+1):
    print(ans[i])

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,s0 = map(int,input().split())
s0 = min(2500,s0)
G = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  u-=1;v-=1
  G[u].append((v,-a,b))
  G[v].append((u,-a,b))
for i in range(n):
  c,d = map(int,input().split())
  G[i].append((i,c,d))

def dijktra(g,s):
    n=len(g)
    dist = [[inf]*2501 for i in range(n)]
    dist[s][s0] = 0
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
        time,money,u = heapq.heappop(hq)
        if dist[u][money] < time: continue
        for v,money1,time1 in g[u]:
          M = min(2500,money+money1)
          if not M >= 0: continue
          if dist[v][M] > time + time1:
            dist[v][M] = (time + time1)
            heapq.heappush(hq,(time + time1, M,v))
    return dist

dist = dijktra(G,0)
for i in range(1,n):
  print(min(dist[i]))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dijkstra(nodes: list, src: int) -> list:
    from heapq import heappush, heappop

    N = len(nodes)
    MAX = 50**2
    res = list2d(N, MAX+1, INF)
    que = [(0, src, min(S, MAX))]
    res[src][min(S, MAX)] = 0
    while que:
        dist, u, coin  = heappop(que)
        if res[u][coin] < dist:
            continue
        if dist + D[u] < res[u][min(coin+C[u], MAX)]:
            res[u][min(coin+C[u], MAX)] = dist + D[u]
            heappush(que, (dist+D[u], u, min(coin+C[u], MAX)))
        for v, a, b in nodes[u]:
            if coin - a >= 0 and dist + b < res[v][coin-a]:
                res[v][coin-a] = dist + b
                heappush(que, (dist+b, v, coin-a))
    return res

N, M, S = MAP()
nodes = [[] for i in range(N)]
for _ in range(M):
    u, v, a, b = MAP()
    u -= 1; v -= 1
    nodes[u].append((v, a, b))
    nodes[v].append((u, a, b))
C = [0] * N
D = [0] * N
for i in range(N):
    c, d = MAP()
    C[i] = c
    D[i] = d

res = dijkstra(nodes, 0)
for i in range(1, N):
    print(min(res[i]))

Solution (Python):
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


N, M, S = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(M)]
cd = [list(map(int, input().split())) for i in range(N)]

max_a = max([x[2] for x in uvab])
num_coins = max_a * M 
num_states = N * (num_coins + 1) 

d = []
row = []
col = []

for u, v, a, b in uvab:
  u -= 1; v -= 1
  i = (num_coins + 1) * u
  j = (num_coins + 1) * v
  for n in range(a, num_coins+1):
    d.extend([b, b])
    row.extend([i+n, j+n])
    col.extend([j+n-a, i+n-a])

for i, _cd in enumerate(cd):
  get, time = _cd
  start = i * (num_coins + 1)
  end = (i + 1) * (num_coins + 1)
  for j in range(start, end):
    if j + get < end:
      d.append(time)
      row.append(j)
      col.append(j + get)
    else:
      break

g = csr_matrix((d, (row, col)), shape=(num_states, num_states))

start_idx = min(S, num_coins)
dist = dijkstra(g, indices=start_idx).astype(int)
ans = []
for i in range(1, N):
  start = i * (num_coins + 1)
  end = (i + 1) * (num_coins + 1)
  _ans = float('inf')
  for j in range(start, end):
    _ans = min(_ans, dist[j])
  ans.append(_ans)

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

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache

import heapq






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N,M,S = inputIL()

L = [[] for i in range(N+1)]

for _ in range(M):
  U,V,A,B = inputIL()
  L[U].append((V,A,B))
  L[V].append((U,A,B))
  
T = [(0,0)]

for _ in range(N):
  C,D = inputIL()
  T.append((C,D))
  
MAX = (N-1)*50

S = min(MAX,S)

dic = {}

for i in range(1,N+1):
  for s in range(MAX+1):
    dic[(i,s)] = []
    for item in L[i]:
      j,a,b = item
      if s >= a:
        dic[(i,s)].append(((j,s-a),b))
    c,d = T[i]
    dic[(i,s)].append(((i,min(s+c,MAX)),d))
    
a = [key for key in dic]

      

d = [[float("inf") for s in range(MAX+1)] for i in range(1,N+2)]
d[1][S] = 0
q = [(0,(1,S))]

while(len(q) != 0):
  ci,temp = heapq.heappop(q)
  i,s = temp
  if d[i][s]<ci:
    continue
  for item in dic[(i,s)]:
    temp,cj = item
    j,t = temp
    if d[j][t] > d[i][s] + cj:
      d[j][t] = d[i][s] + cj
      heapq.heappush(q,(d[j][t], (j,t)))

for item in d[2:]:
  print(min(item))

Solution (Python):


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


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

cd_list = []
for i in range(N):
    C, D = map(int, input().split())
    cd_list.append((C, D))

edge = { }
for U, V, A, B in uvab_list:
    for j in range(2501):  
        if j - A >= 0:
            if not (U, j) in edge:
                edge[(U, j)] = []
            edge[(U, j)].append((B, (V, j - A)))
            if not (V, j) in edge:
                edge[(V, j)] = []
            edge[(V, j)].append((B, (U, j - A)))



for i in range(N):
    C, D = cd_list[i]
    for j in range(2501):
        if not (i + 1, j) in edge:
            edge[(i + 1, j)] = []
        jj = min(2500, j + C)
        edge[(i + 1, j)].append((D, (i + 1, jj)))

import heapq
def dijkstra_heap(p):
    vlist=[]
    for i in range(1,N+1):
        for j in range(2501):
            vlist.append((i,j))
    d = {}
    used = {}
    INF = float("inf")
    for v in vlist:
        used[v] = True
        d[v] = INF
    
    d[p] = 0
    used[p] = False

    edgelist = []
    for e in edge[p]:
        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




res = dijkstra_heap((1,S))
final_result = [float("inf")]*N

for p in res:
    if final_result[p[0]-1] > res[p]:
        final_result[p[0]-1] = res[p]

for r in final_result[1:]:
    print(r)