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 heapq
from collections import defaultdict as dd
from bisect import bisect_left
N, M, S = map(int, input().split())
costs = dd(dict)
times = dd(dict)
MAX = 0
for _ in range(M):
    u, v, a, b = map(int, input().split())
    MAX += a
    costs[u][v] = costs[v][u] = a
    times[u][v] = times[v][u] = b
Cs = [0]
Ds = [0]
for _ in range(N):
    c, d = map(int, input().split())
    Cs.append(c)
    Ds.append(d)

thres = [[] for _ in range(N+1)]
vals = [[] for _ in range(N+1)]

q = []
heapq.heappush(q, (0, 1, S))
while q:
    if all(thres):
        break
    c, i, m = heapq.heappop(q)
    if thres[i] and thres[i][-1] >= m:
        continue
    thres[i].append(m)
    vals[i].append(c)
    for to in costs[i].keys():
        cost = costs[i][to]
        t = times[i][to]
        if m >= cost:
            heapq.heappush(q, (c+t, to, m-cost))

    if m < MAX:
        heapq.heappush(q, (c+Ds[i], i, m+Cs[i]))

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

Solution (Python):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  
        self._E = 0  
        self._V = V  

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  
                    heapq.heappush(que, (d[e.to], e.to))  
        return d

N,M,S=map(int,input().split())
pro=Dijkstra(N*5001)
for i in range(0,M):
    u,v,a,b=map(int,input().split())
    for j in range(a,5001):
        pro.add(N*j+u-1,N*(j-a)+v-1,b)
        pro.add(N*j+v-1,N*(j-a)+u-1,b)

for i in range(0,N):
    c,d=map(int,input().split())
    for j in range(0,5000):
        to=min(5000,j+c)
        pro.add(N*j+i,N*to+i,d)

S=min(5000,S)
ans=pro.shortest_path(N*S)
for i in range(1,N):
    p=float("inf")
    for j in range(0,5001):
        p=min(p,ans[N*j+i])
    print(p)

Solution (Python):
import heapq

INF = 10**20
A = 50  


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


def main():
    N, M, S = inpl()
    S = min(S, M * A)

    lines = [[] for _ in range(N * (M * A + 1))]
    for _ in range(M):
        in_s, in_t, cost, time = inpl()
        in_s -= 1
        in_t -= 1

        for n in range(cost, M * A + 1):
            s = in_s + n * N
            t = in_t + (n - cost) * N
            lines[s].append((t, time))

            s = in_s + (n - cost) * N
            t = in_t + n * N
            lines[t].append((s, time))

    for i in range(N):
        cost, time = inpl()
        for n in range(0, M * A + 1):
            s = i + n * N
            if n + cost > M * A:
                t = i + (M * A) * N
            else:
                t = i + (n + cost) * N
            lines[s].append((t, time))

    def dijkstra(N, S):
        weight = [INF] * N
        weight[S] = 0
        q = [[0, S]]
        heapq.heapify(q)
        while q:
            w0, s = heapq.heappop(q)
            for t, w in lines[s]:
                w += w0
                if weight[t] > w:
                    heapq.heappush(q, [w, t])
                    weight[t] = w

        return weight

    weight = dijkstra(N * (M * A + 1), 0 + S * N)

    ansl = [INF] * N
    for i, w in enumerate(weight):
        n = i % N
        if n == 0:
            continue
        else:
            ansl[n] = min(w, ansl[n])

    print("\n".join(map(str, ansl[1:])))


if __name__ == "__main__":
    main()

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

links = [[] for _ in range(5001 * n)]
for tmp in uvab:
    u,v,a,b = tmp
    u -= 1
    v -= 1
    for i in range(4999,0,-1):
        if(i-a >= 0):
            links[u*5001+i].append((b, v*5001+i-a))
            links[v*5001+i].append((b, u*5001+i-a))
        else:
            break
    links[u*5001+5000].append((b, v*5001+5000))
    links[v*5001+5000].append((b, u*5001+5000))

for i,tmp in enumerate(cd):
    c,d = tmp
    for j in range(5000):
        links[i*5001+j].append((d ,i*5001 + min(j+c, 5000)))


import heapq
def dijkstra(links, start, n):
    inf = 10**10
    d = [inf] * (n)
    d[start] = 0
    hq = []
    used = set()
    used.add(start)
    for i in links[start]:
        heapq.heappush(hq, i)
    while(hq):
        cost,i = heapq.heappop(hq)
        if( i in used):
            continue
        d[i] = cost
        used.add(i)
        for tmp in links[i]:
            cost_next, j = tmp
            if(not j in used):
                heapq.heappush(hq, (cost+cost_next, j))
    return d

s = min(s, 5000)
d = dijkstra(links, s, 5001*n)
for i in range(1,n):
    ans = d[i*5001]
    for j in range(1,5001):
        ans = min(ans, d[i*5001+j])
    print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
N, M, S = map(int, readline().split())

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    
    inf = 10**18
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                hp(Q, (dn + df,vf))
    return dist

geta = 2451
Edge = [[] for _ in range(N*geta)]
S = min(S, geta - 1)
for m in range(M):
    u, v, a, b = map(int, readline().split())
    u -= 1
    v -= 1
    for mon in range(a, geta):
        Edge[u*geta+mon].append((b, v*geta + (mon - a)))
        Edge[v*geta+mon].append((b, u*geta + (mon - a)))

for n in range(N):
    c, d = map(int, readline().split())
    for mon in range(geta):
        Edge[n*geta + mon].append((d, n*geta + min(geta-1, mon + c)))

dist = dijkstra(N*geta, S, Edge) 
INF = 10**18
ans = [INF]*N
for i in range(N*geta):
    ans[i//geta] = min(ans[i//geta], dist[i])
print('\n'.join(map(str, ans[1:])))

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

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = map(int, input().split())
    AB = [[None] * N for _ in range(N)]
    s = 0
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
        s += A
    MAX = s + 1
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    for v in range(1, N):
        print(min(dist[v*MAX:(v+1)*MAX]))
main()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    import heapq
    input = sys.stdin.buffer.readline

    def dijkstra(adj, start):
        
        inf = 1 << 60
        dist = [inf] * len(adj)
        dist[start] = 0
        q = []
        heapq.heappush(q, (0, start))
        while q:
            min_dist, v_from = heapq.heappop(q)
            if min_dist > dist[v_from]:
                continue
            v_tos = adj[v_from]
            for v_to, cost in v_tos:
                if min_dist + cost < dist[v_to]:
                    dist[v_to] = min_dist + cost
                    heapq.heappush(q, (dist[v_to], v_to))
        return dist

    N, M, S = map(int, input().split())
    K = 5001
    adj = [[] for _ in range(N * K + 1)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        for j in range(a, K):
            uu = (u-1) * K + j + 1
            vv = (v-1) * K + (j-a) + 1
            adj[uu].append((vv, b))
            uu = (u - 1) * K + (j-a) + 1
            vv = (v - 1) * K + j + 1
            adj[vv].append((uu, b))
    for i in range(1, N+1):
        c, d = map(int, input().split())
        for j in range(K-1):
            adj[(i-1) * K + j + 1].append(((i-1) * K + min(j+c, K-1) + 1, d))

    S = min(5000, S)
    dist = dijkstra(adj, S + 1)
    for v in range(2, N+1):
        ans = 10**18
        for j in range(K):
            ans = min(ans, dist[(v-1) * K + j + 1])
        print(ans)


if __name__ == '__main__':
    main()

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

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

print('\n'.join(map(str, ans[1:])))

Solution (Python):
n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
heappush(pq,(0,s*n))
while pq:
    weight,u = heappop(pq)
    if d[u]>weight:
        d[u]=weight
        for v,weight in edge[u]:
            heappush(pq,(d[u]+weight,v))
for i in range(1,n):
    print(d[i])

Solution (Python):
n, m, s = map(int,input().split())
adj = [[] for i in range(n)]
for _ in range(m):
    u, v, a, b = map(int,input().split())
    adj[u - 1].append((v - 1,-a,b))
    adj[v - 1].append((u - 1,-a,b))

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

out = [-1] * n
count = 0

LARGE = 50 * n

done = dict()
from heapq import *
q = []
if s > LARGE:
    s = LARGE
heappush(q, (0, 0, s))

while q:
    time, loc, curr = heappop(q)
    if out[loc] == -1:
        out[loc] = time
        count += 1
        if count == n:
            break
    for nex, cost, timeD in adj[loc]:
        currNex = curr + cost
        timeNex = time + timeD
        if currNex > LARGE:
            currNex = LARGE
        if currNex < 0:
            continue
        if (nex, currNex) not in done or timeNex < done[(nex, currNex)]:
            done[(nex, currNex)] = timeNex
            heappush(q, (timeNex, nex, currNex))
print(*out[1:], sep = '\n')

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

N, M, S = map(int, input().split())
STATE = 50 * N + 1
vec = [[] for _ in range(STATE * N)]
for _ in range(M) :
  U, V, A, B = map(int, input().split())
  U -= 1
  V -= 1
  for silver in range(A, STATE) :
    vec[STATE * U + silver].append((STATE * V + silver - A, B))
    vec[STATE * V + silver].append((STATE * U + silver - A, B))
  
for i in range(N) :
  C, D = map(int, input().split())
  for silver in range(STATE - C) :
    vec[STATE * i + silver].append((STATE * i + silver + C, D))

dist = [float('inf')] * (STATE * N)

S = min(S, STATE - 1)
dist[S] = 0
q = [(0, S)]
while q :
  cc, cur = heappop(q)
  for nex, nc in vec[cur] :
    if dist[nex] <= cc + nc :
      continue
    dist[nex] = cc + nc
    heappush(q, (cc + nc, nex))

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

Solution (Python):
import sys
range = xrange
input = raw_input

M = 2501
inf = 3 * 10**18

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0
n = inp[ii]; ii += 1
m = inp[ii]; ii += 1
s = inp[ii]; ii += 1

s = min(M - 1, s)

coupl = [[] for _ in range(n)]
V = []
A = []
B = []
for _ in range(m):
    u = inp[ii] - 1; ii += 1
    v = inp[ii] - 1; ii += 1
    coupl[u].append(2 * _)
    coupl[v].append(2 * _ + 1)
    V.append(v)
    V.append(u)

    A.append(inp[ii]); ii += 1
    B.append(inp[ii]); ii += 1

C = inp[ii + 0: ii + 2 * n: 2]
D = inp[ii + 1: ii + 2 * n: 2]
ii += n

import heapq
DP = [inf] * (n * M)
found = [0] * (n * M)
DP[s] = 0


queue = [(0,s)]
while queue:
    _,ind = heapq.heappop(queue)
    if found[ind]:
        continue
    found[ind] = 1
    node,money = divmod(ind, M)
    for eind in coupl[node]:
        v = V[eind]
        ind2 = ind - A[eind >> 1] + M*(v - node)
        if money >= A[eind >> 1] and not found[ind2]:
            val = DP[ind] + B[eind >> 1]
            if DP[ind2] > val:
                DP[ind2] = val
                heapq.heappush(queue, (val, ind2))

    ind2 = ind - money + min(M - 1, C[node] + money)
    val = DP[ind] + D[node]
    if DP[ind2] > val:
        DP[ind2] = val
        heapq.heappush(queue, (val, ind2))

ans = []
for node in range(1, n):
    ans.append(min(DP[node * M + m] for m in range(M)))
print '\n'.join(str(x) for x in ans)

Solution (Python):

"""

銀貨の枚数,時間で最小値を計算推移？
Sがでかいなら普通に最小距離　おｋ

Sが小さい時
島をcostmax+1個に分ける
→dijkstraで解ける

"""
from collections import deque
N,M,S = map(int,input().split())

lis = [ [] for i in range(N) ]
costsum = 0

for i in range(M):

    U,V,A,B = map(int,input().split())
    U -= 1
    V -= 1

    lis[U].append([V,A,B])
    lis[V].append([U,A,B])

    costsum += A

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

if S >= costsum:

    q = deque([0])
    dis = [float("inf")] * N
    dis[0] = 0

    while len(q) > 0:
        now = q.popleft()
        for i in range(len(lis[now])):
            nex,a,b = lis[now][i]

            if dis[nex] > dis[now] + b:
                dis[nex] = dis[now] + b
                q.append(nex)

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

else:

    import heapq

    dis = [ [float("inf")] * (costsum+1) for i in range(N) ]
    able = [ [True]  * (costsum+1) for i in range(N) ]
    end = 0
    q = [[0,0,S]]
    dis[0][S] = 0

    while len(q) > 0:
        
        if end == (costsum+1)*N:
            break

        ncost,nv,ns = heapq.heappop(q)
        if not able[nv][ns]:
            continue
        able[nv][ns] = False
        end += 1

        for i in range(len(lis[nv])):

            nex,a,b = lis[nv][i]

            if ns >= a and dis[nex][ns-a] > dis[nv][ns] + b:
                dis[nex][ns-a] = dis[nv][ns] + b
                heapq.heappush(q,[dis[nex][ns-a] , nex , ns-a])

        pl = 1
        C,D = CD[nv]
        if ns+C<=costsum and dis[nv][ns+pl*C] > dis[nv][ns] + D:
            dis[nv][ns+pl*C] = dis[nv][ns] + D
            heapq.heappush(q, [dis[nv][ns+pl*C],nv,ns+pl*C])

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

Solution (Python):
def main():
    from collections import deque

    import sys
    input = sys.stdin.readline

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

    S = min(S, 50 * 50) 

    G = [[] for _ in range(N + 1)]

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

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

    MAX = 10 ** 18
    DP = [[MAX] * (50 * 50 + 1) for _ in range(N + 1)]

    
    

    
    for s in range(S + 1):
        DP[1][s] = 0
    for s in range(S + 1, 50 * 50 + 1):
        DP[1][s] = DP[1][max(0, s - CD[0][0])] + CD[0][1]

    que = deque()
    que.append(1)

    while que:
        tmp = que.popleft()
        for v, a, b in G[tmp]:
            flag = False
            for i in range(50 * 49 + 1):
                if DP[v][i] > DP[tmp][i + a] + b:
                    flag = True
                    DP[v][i] = DP[tmp][i + a] + b
            c = CD[v - 1][0]
            d = CD[v - 1][1]
            if flag:
                for i in range(50 * 50 + 1):
                    DP[v][i] = min(DP[v][i], DP[v][max(0, i - c)] + d)
                que.append(v)

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

    
                
    
    

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, S = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1
  v -= 1
  for x in range(a, 2501):
    e[N * x + u].append((N * (x - a) + v, b))
    e[N * x + v].append((N * (x - a) + u, b))
for i in range(N):
  c, d = map(int, input().split())
  for x in range(2501):
    e[N * x + i].append((N * min(2500, x + c) + i, d))
import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d

dij = dijkstra(2501 * N, e)
p = dij.path(min(S, 2500) * N, 0)
for i in range(1, N):
  res = float("inf")
  for j in range(2501):
    res = min(res, p[i + N * j])
  print(res)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict
from heapq import heappop, heappush

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


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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append((b, w))

	def get_nodes(self):
		return self.graph.keys()

class Dijkstra(object):
	def __init__(self, graph, s):
		self.g = graph.graph
		self.dist = defaultdict(lambda: INF)
		self.dist[s] = 0
		self.Q = []
		heappush(self.Q, (self.dist[s], s))

		while self.Q:
			dist_u, u = heappop(self.Q)
			if self.dist[u] < dist_u:
				continue
			for v, w in self.g[u]:
				alt = dist_u + w
				if self.dist[v] > alt:
					self.dist[v] = alt
					heappush(self.Q, (alt, v))



def main():
	N, M, S = getlist()
	G = Graph()
	
	for _ in range(M):
		U, V, A, B = getlist()
		for i in range(2500 - A + 1):
			G.add_edge(U * (10 ** 5) + 2500 - i, V * (10 ** 5) + 2500 - A - i, B)
			G.add_edge(V * (10 ** 5) + 2500 - i, U * (10 ** 5) + 2500 - A - i, B)

	for i in range(N):
		
		C, D = getlist()
		for j in range(2500):
			G.add_edge((i + 1) * (10 ** 5) + j, (i + 1) * (10 ** 5) + min(j + C, 2500), D)

	
	D = Dijkstra(G, 10 ** 5 + min(2500, S))

	for i in range(2, N + 1):
		ans = INF
		for j in range(2501):
			ans = min(D.dist[i * (10 ** 5) + j], ans)
		print(ans)
	




if __name__ == '__main__':
	main()

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

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

C=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]
DP=[[1<<60]*5001 for i in range(51)]

import heapq

Q=[(0,min(S,5000),1)]
DP[1][min(S,5000)]=0

while Q:
    time,money,town = heapq.heappop(Q)

    for to,pmoney,ptime in E[town]:
        if money>=pmoney and DP[to][money-pmoney]>time+ptime:
            DP[to][money-pmoney]=time+ptime
            heapq.heappush(Q,(time+ptime,money-pmoney,to))
            
    if DP[town][min(money+C[town][0],5000)]>time+C[town][1]:
        DP[town][min(money+C[town][0],5000)]=time+C[town][1]
        heapq.heappush(Q,(time+C[town][1],min(money+C[town][0],5000),town))
        
for i in range(2,N+1):
    print(min(DP[i]))

Solution (Python):


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

n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))


cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]


from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] 
dist[0][s] = 0
q = [(0,s,0)] 

while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    

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

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n, m, s = nm()
N = n * 3001
G = [list() for _ in range(N)]
for _ in range(m):
    u, v, a, b = nm()
    u -= 1; v -= 1
    for j in range(0, N, n):
        if v + j - a * n >= 0:
            G[u + j].append((v + j - a * n, b))
        if u + j - a * n >= 0:
            G[v + j].append((u + j - a * n, b))
for u in range(n):
    c, d = nm()
    for j in range(0, N, n):
        G[u + j].append((min(u + j + c * n, u + N - n), d))

import heapq as hq

def dijkstra(G, s, t=None):
    """
    G[v] = [(x1, c1), (x2, c2), ...]
    """
    dist = [1<<60]*len(G)
    dist[s] = 0
    q = [(0, s)]
    while q:
        d, v = hq.heappop(q)
        if d > dist[v]: continue
        for x, c in G[v]:
            if dist[x] > d + c:
                dist[x] = d + c
                hq.heappush(q, (d + c, x))
    if t is None:
        return dist
    else:
        return dist[t]

dist = dijkstra(G, min(s, 3000) * n)
for i in range(1, n):
    print(min(dist[i::n]))

Solution (Python):
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, S = map(int, input().split())
k = 2451
X = [[] for _ in range(N * k)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    for i in range(a, k):
        X[u * k + i].append([v * k + i - a, b])
        X[v * k + i].append([u * k + i - a, b])

for i in range(N):
    c, d = map(int, input().split())
    for j in range(k - 1):
        X[i * k + j].append([i * k + min(j + c, k - 1), d])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D

D = dijkstra(N * k, X, min(S, k - 1))
print(*[min(D[i * k:(i+1) * k]) for i in range(N)][1:], sep = "\n")

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

def dijkstra(sta):
    dist = [10**18]*(N*2510)
    dist[sta] = 0
    pq = []
    heappush(pq, (dist[sta], sta))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    return dist

N, M, S = map(int, input().split())
serial = [[0]*2510 for _ in range(N)]
c = 0

for i in range(N):
    for j in range(2510):
        serial[i][j] = c
        c += 1

G = [[] for _ in range(N*2510)]

for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    
    for i in range(a, 2510):
        G[serial[u][i]].append((serial[v][i-a], b))
        G[serial[v][i]].append((serial[u][i-a], b))

for i in range(N):
    c, d = map(int, input().split())
    
    for j in range(2510):
        if j+c<2510:
            G[serial[i][j]].append((serial[i][j+c], d))

dist = dijkstra(serial[0][min(S, 2509)])

for i in range(1, N):
    ans_i = 10**18
    
    for j in range(2510):
        ans_i = min(ans_i, dist[serial[i][j]])
    
    print(ans_i)