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 heapq import heappop,heappush
inf = float("inf")

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

G = [[] for _ in range(n)]
for _ in range(m):
    u,v,cost,time = map(int,input().split())
    u -= 1
    v -= 1
    G[u].append((v,cost,time))
    G[v].append((u,cost,time))

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



mint = [[inf]*2451 for _ in range(n)]



white = 0
black = 1
color = [[white]*2451 for _ in range(n)]

def dijkstra(u,s):
    
    s = min(s,2450)
    mint[u][s] = 0
    color[u][s] = black

    PQ = []
    heappush(PQ,(0,u,s))
    while PQ:
        
        
        
        minv,now,nowcoins = heappop(PQ)
        color[now][nowcoins] = black
        
        if mint[now][nowcoins] < minv: continue
        
        
        
        
        
        for nxt,cost,time in G[now]:
            nxtcoins = min(nowcoins - cost,2450)
            if nxtcoins < 0: continue
            if color[nxt][nxtcoins]: continue
            if mint[nxt][nxtcoins] > minv + time:
                mint[nxt][nxtcoins] = minv + time
                heappush(PQ,(mint[nxt][nxtcoins],nxt,nxtcoins))

dijkstra(0,s)



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

Solution (Python):
[print(min(m[i])[0])for h in [__import__('heapq')]for a,d,r,n,x in[(h.heappush,h.heappop,range,lambda:map(int,input().split()),list.append)]for N,M,S in[n()]for g,q in[([[]for _ in r(N)],[(0,S,0)])]for L in[max(A for _ in r(M)for U,V,A,B in[n()]if not(x(g[U-1],(V-1,A,B))or x(g[V-1],(U-1,A,B))))*(N-1)]for m in[[[[2**64]for _ in r(L+1)]for _ in r(N)]]for _ in[[[x(g[i],(i,-C,D))for i in r(N)for C,D in[n()]],[[[_ for s,v,i in[d(q)]for _ in[[a(q,(s+c,j,t))for t,p,c in g[i]for j in[min(L,v-p)]for y in[m[t][j]]if v>=p and s+c<y[0] and not(y.clear()or x(y,s+c))]]if not(x(l,None)if q else l.clear())]]for l in[[None]]for _ in l]]]for i in r(1,N)]

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 13
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from heapq import heapify,heappop,heappush

def dijkstra(G,s = 0): 
    n = len(G)
    dist = [INF] * n
    dist[s] = 0

    q = [(0,s)]
    heapify(q)

    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for e,cost in G[v]:
            if dist[e] > dist[v] + cost:
                dist[e] = dist[v] + cost
                heappush(q,(dist[e],e))
    
    return dist

def main():
    n,m,s = map(int,input().split())
    MAXV = 2500*n
    G = [[] for _ in range(MAXV)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v -= 1
        for i in range(2500 - a):
            G[u*2500 + i + a].append((v*2500 + i,b))
            G[v*2500 + i + a].append((u*2500 + i,b))
    
    for i in range(n):
        c,d = map(int,input().split())
        for j in range(2500 - c):
            G[i*2500 + j].append((i*2500 + j + c,d))
  
    dist = dijkstra(G,min(s,2499))
    for i in range(1,n):
        ans = min(dist[2500*i:2500*(i + 1)])
        print(ans) 

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, cost, dist = map(int, input().split())
    mxCost = max(mxCost, cost)
    fr -= 1
    to -= 1
    edges[fr].append((to, dist, cost))
    edges[to].append((fr, dist, cost))

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

que = [(0, S, 0)]
mxCost *= (N - 1)
minDsit = [[10**18] * (mxCost + 1) for _ in range(N)]
minDsit[0][0] = 0

while que:
    dist, s, now = heappop(que)

    for to, d, c in edges[now]:
        cost = min(mxCost, s - c)
        if cost < 0 or minDsit[to][cost] <= dist + d:
            continue
        minDsit[to][cost] = dist + d
        heappush(que, (dist + d, cost, to))

for dist in minDsit[1:]:
    print(min(dist))

Solution (Python):
def main():
    import heapq
    
    def dijkstra(graph,s,cd,c):
        dist = [[float("inf")]*2505 for _ in range(n)]
        q = []
        dist[s][c] = 0
        heapq.heappush(q, (0,s,c))
        
        while q:
            d, p,c = heapq.heappop(q)
            
            if dist[p][c] < d:
                continue
            if c+cd[p][0] < 2500:
                if dist[p][c+cd[p][0]] >  d+cd[p][1]:
                    dist[p][c+cd[p][0]] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,c+cd[p][0]))
            else:
                if dist[p][2500] >  d+cd[p][1]:
                    dist[p][2500] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,2500))
            for nn,nc,nt  in graph[p]:
                if c >= nc and dist[nn][c-nc] >   d+nt:
                    dist[nn][c-nc] =    d+nt
                    heapq.heappush(q,(d+nt,nn,c-nc))
            
                    
        for i in dist[1:]:
            print(min(i))
    n,m,s = map(int,input().split())
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v-= 1
        la.append(a)
        E[u].append((v,a,b))
        E[v].append((u,a,b))

    cd = [list(map(int,input().split())) for i in range(n)]

    dijkstra(E,0,cd,min(s,2500))
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import heapq
    
    def dijkstra(graph,s,cd,c):
        dist = [[float("inf")]*2505 for _ in range(n)]
        q = []
        dist[s][c] = 0
        heapq.heappush(q, (0,s,c))
        
        while q:
            d, p,c = heapq.heappop(q)
            
            if dist[p][c] < d:
                continue
            
            for nn,nc,nt  in graph[p]:
                if c >= nc and dist[nn][c-nc] >   d+nt:
                    dist[nn][c-nc] =    d+nt
                    heapq.heappush(q,(d+nt,nn,c-nc))
            if c+cd[p][0] < 2500:
                if dist[p][c+cd[p][0]] >  d+cd[p][1]:
                    dist[p][c+cd[p][0]] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,c+cd[p][0]))
            else:
                if dist[p][2500] >  d+cd[p][1]:
                    dist[p][2500] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,2500))
                    
        for i in dist[1:]:
            print(min(i))
    n,m,s = map(int,input().split())
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v-= 1
        la.append(a)
        E[u].append((v,a,b))
        E[v].append((u,a,b))

    cd = [list(map(int,input().split())) for i in range(n)]

    dijkstra(E,0,cd,min(s,2500))
if __name__ == "__main__":
    main()

Solution (Python):
z=lambda i,c:i+c*50;n,m,s=map(int,input().split());e=[[]for _ in range(4**9)];from heapq import*;t=z(0,min(2500,s));d=[9**20]*(4**9);d[t]=0;h=[[0,t]];q=[9**20]*(n-1)
for _ in range(m):
  u,v,a,b=map(int,input().split())
  for i in range(a,2501):e[z(u-1,i)].append((z(v-1,i-a),b));e[z(v-1,i)].append((z(u-1,i-a),b))
for i in range(n):
  c,r=map(int,input().split())
  for j in range(c,2501):e[z(i,j-c)].append((z(i,j),r))
while h:
  c,v=heappop(h)
  if d[v]<c:continue
  for u,t in e[v]:
    if c+t<d[u]:d[u]=c+t;heappush(h,[c+t,u])
for i in range(n-1):
  for j in range(2501):q[i]=min(q[i],d[z(i+1,j)])
print(*q)

Solution (Python):
import heapq



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

edge = [[] for i in range(n)]



Cs=[]
Ds=[]
amax=0
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])
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    return min(S,dg)

S=cut(S)

def dijkstra(start):

    
    
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,[Ds[0], 0, cut(S+Cs[0])])

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,[e[2],e[0],S-e[1]])

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            
            if d[ce][ns]==10**20:
                
                heapq.heappush(edgelist, [t+Ds[ce],ce,ns])

            for e in edge[ce]:
                if cs>=e[1]:
                    
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        
                        heapq.heappush(edgelist, [t+e[2],ne,ns])
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))

Solution (Python):
import heapq



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

edge = [[] for i in range(n)]



Cs=[]
Ds=[]
amax=0
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])
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    return min(S,dg)

S=cut(S)

def dijkstra(start):

    
    
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,[Ds[0], 0, cut(S+Cs[0])])

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,[e[2],e[0],S-e[1]])

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            
            if d[ce][ns]==10**20:
                
                heapq.heappush(edgelist, [t+Ds[ce],ce,ns])

            for e in edge[ce]:
                if cs>=e[1]:
                    
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        
                        heapq.heappush(edgelist, [t+e[2],ne,ns])
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))

Solution (Python):
import heapq



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

edge = [[] for i in range(n)]



Cs=[]
Ds=[]
amax=0
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])
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    return min(S,dg)

S=cut(S)

def dijkstra(start):

    
    
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,(Ds[0], 0, cut(S+Cs[0])))

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,(e[2],e[0],S-e[1]))

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            
            if d[ce][ns]==10**20:
                
                heapq.heappush(edgelist, (t+Ds[ce],ce,ns))

            for e in edge[ce]:
                if cs>=e[1]:
                    
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        
                        heapq.heappush(edgelist, (t+e[2],ne,ns))
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))

Solution (Python):
import heapq



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

edge = [[] for i in range(n)]



Cs=[]
Ds=[]
amax=0
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])
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    if S>dg:
        return dg
    else: return S

S=cut(S)

def dijkstra(start):

    
    
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,(Ds[0], 0, cut(S+Cs[0])))

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,(e[2],e[0],S-e[1]))

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            
            if d[ce][ns]==10**20:
                
                heapq.heappush(edgelist, (t+Ds[ce],ce,ns))

            for e in edge[ce]:
                if cs>=e[1]:
                    
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        
                        heapq.heappush(edgelist, (t+e[2],ne,ns))
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, m, s = LI()
s = min(s, 2500)
uvab = [LI() for _ in range(m)]
cd = [LI() for _ in range(n)]
dp = [[inf]*(2500+1) for _ in range(n+1)]
dp[0][s] = 0
edges = [[] for _ in range(n)]
exchange = [[c,d] for c,d in cd]
for u,v,a,b in uvab:
    edges[u-1].append((v-1, a, b))
    edges[v-1].append((u-1, a, b))
for i, (c,d) in enumerate(cd):
    edges[i].append((i, -c, d))

h = [(0, 0, s)]
while h:
    dist, u, coin = heappop(h)
    if dp[u][coin] < dist:
        continue
    for v, a, b in edges[u]:
        if 2500 >= coin-a >= 0:
            if dp[u][coin] + b < dp[v][coin-a]:
                dp[v][coin-a] = dp[u][coin] + b
                heappush(h,(dp[v][coin-a], v, coin-a))

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

Solution (Python):
import heapq
n, m, s = map(int, input().split())
s = min(s, 2499)
UV = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    UV[u].append((v, a, b))
    UV[v].append((u, a, b))
CD = [tuple(map(int, input().split()))for _ in range(n)]
MAXS = 2500
NV = MAXS*n
edges = [[] for _ in range(NV)]


def to_v(i, j):
    return MAXS*i+j

for i, (c, d) in enumerate(CD):
    for j in range(MAXS-c):
        edges[to_v(i, j)].append((d, to_v(i, j)+c))

for i in range(n):
    for i2, a, b in UV[i]:
        for j in range(MAXS-a):
            edges[to_v(i, a+j)].append((b, to_v(i2, j)))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*NV
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


INF = 10**18
dist = dijkstra(s)
for i in range(1, n):
    ans = INF
    for j in range(MAXS):
        ans = min(ans, dist[to_v(i, j)])
    print(ans)

Solution (Python):
def main():
    import heapq
    
    def dijkstra(graph,start,cd,s):
        dist = [[float("inf")]*2505 for _ in range(n)]
        q = []
        dist[start][s] = 0
        heapq.heappush(q, (0,start,s))
        
        while q:
            cost, cur_node,coin = heapq.heappop(q)
            
            if dist[cur_node][coin] < cost:
                continue
            
            for nex_node,nex_cost,nex_time  in graph[cur_node]:
                if coin >= nex_cost and dist[nex_node][coin-nex_cost] > cost+nex_time:
                    dist[nex_node][coin-nex_cost] = cost+nex_time
                    heapq.heappush(q, (cost+nex_time,nex_node,coin-nex_cost))
            if dist[cur_node][min(2500,coin+cd[cur_node][0])] > cost+cd[cur_node][1]:
                 dist[cur_node][min(2500,coin+cd[cur_node][0])] = cost+cd[cur_node][1]
                 heapq.heappush(q,(cost+cd[cur_node][1],cur_node,min(2500,coin+cd[cur_node][0])))
                    
        for i in dist[1:]:
            print(min(i))
    n,m,s = map(int,input().split())
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v-= 1
        la.append(a)
        E[u].append((v,a,b))
        E[v].append((u,a,b))

    cd = [list(map(int,input().split())) for i in range(n)]

    dijkstra(E,0,cd,min(s,2500))
if __name__ == "__main__":
    main()

Solution (Python):
import heapq
n, m, s = map(int, input().split())
s = min(s, 2499)
UV = [[] for _ in range(n)]
A_cost = []
B_dist = []
for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    UV[u].append((v, i))
    UV[v].append((u, i))
    A_cost.append(a)
    B_dist.append(b)

C_income = []
D_dist = []
for _ in range(n):
    c, d = map(int, input().split())
    C_income.append(c)
    D_dist.append(d)

NV = 2500*n
edges = [[] for _ in range(NV)]

for i in range(n):
    c = C_income[i]
    d = D_dist[i]
    for j in range(2500-c):
        edges[2500*i+j].append((d, 2500*i+j+c))

for i in range(n):
    for j, k in UV[i]:
        a = A_cost[k]
        b = B_dist[k]
        for x in range(2500-a):
            edges[2500*i+x+a].append((b, 2500*j+x))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*(NV)
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


INF = 10**18
dist = dijkstra(s)
for i in range(1, n):
    ans = INF
    for j in range(2500):
        ans = min(ans, dist[2500*i+j])
    print(ans)

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

n,m,s = map(int,input().split())
if s >= 2500:
    s = 2499

dg = 2500
INF = 10**15

dist = [INF]*(n*dg)

edge = [[] for i in range(n)]
a = [0]*m
b = [0]*m

for i in range(m):
    u,v,aa,bb = map(int,input().split())
    a[i] = aa
    b[i] = bb
    edge[u-1].append( (i,v-1))
    edge[v-1].append( (i,u-1) )


c = [0]*n
d = [0]*n

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

tank = [(0,s)]
nonused = [True]*(n*dg)


while tank:
    tim,fr = heapq.heappop(tank)
    if dist[fr] != INF:
        continue
    dist[fr] = tim
    pos,mon = divmod(fr,dg)

    for idx,go in edge[pos]:
        if mon >= a[idx] and dist[go*dg + mon-a[idx]] == INF:
            heapq.heappush(tank,(tim + b[idx] ,go*dg + mon-a[idx] ))
            
    if mon + c[pos] < dg and dist[fr + c[pos]] == INF:
        heapq.heappush(tank,(tim + d[pos] ,fr + c[pos] ))
    elif mon + c[pos] >= dg and dist[pos*dg + dg-1] == INF:
        heapq.heappush(tank,(tim + d[pos] ,pos*dg + dg-1 ))

for i in range(1,n):
    res = INF
    for j in range(dg):
        if dist[i*dg+j] < res:
            res = dist[i*dg+j]
    print(res)

Solution (Python):
from heapq import heappush, heappop

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, cost, dist = map(int, input().split())
    mxCost = max(mxCost, cost)
    fr -= 1
    to -= 1
    edges[fr].append((to, dist, cost))
    edges[to].append((fr, dist, cost))

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

que = [(0, S, 0)]
mxCost *= (N - 1)
minDsit = [[10**18] * (mxCost + 1) for _ in range(N)]
minDsit[0][0] = 0

while que:
    dist, s, now = heappop(que)

    for to, d, c in edges[now]:
        cost = min(mxCost, s - c)
        if cost < 0 or minDsit[to][cost] <= dist + d:
            continue
        minDsit[to][cost] = dist + d
        que.append((dist + d, cost, to))

for dist in minDsit[1:]:
    print(min(dist))

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

n,m,s = map(int,input().split())
if s >= 2500:
    s = 2499

dg = 2500
INF = 10**15

dist = [INF]*(n*dg)

edge = [[] for i in range(n)]
a = [0]*m
b = [0]*m

for i in range(m):
    u,v,aa,bb = map(int,input().split())
    a[i] = aa
    b[i] = bb
    edge[u-1].append( (i,v-1))
    edge[v-1].append( (i,u-1) )


c = [0]*n
d = [0]*n

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

tank = [(0,s)]
nonused = [True]*(n*dg)


while tank:
    tim,fr = heapq.heappop(tank)
    if dist[fr] != INF:
        continue
    dist[fr] = tim
    pos,mon = divmod(fr,dg)

    for idx,go in edge[pos]:
        if mon >= a[idx] and dist[go*dg + mon-a[idx]] == INF:
            heapq.heappush(tank,(tim + b[idx] ,go*dg + mon-a[idx] ))
    if mon + c[pos] < dg and dist[fr + c[pos]] == INF:
        heapq.heappush(tank,(tim + d[pos] ,fr + c[pos] ))

for i in range(1,n):
    res = INF
    for j in range(dg):
        if dist[i*dg+j] < res:
            res = dist[i*dg+j]
    print(res)

Solution (Python):
from heapq import *
N, M, S = tuple(map(int, input().split()))
graph = [[] for _ in range(N)]
Max = 0
for i in range(M):
	U, V, A, B = tuple(map(int, input().split()))
	Max = max(Max, A)
	U -= 1
	V -= 1
	graph[U] += [(V, A, B)]
	graph[V] += [(U, A, B)]
Max *= (N - 1)
for i in range(N):
	C, D = tuple(map(int, input().split()))
	graph[i] += [(i, -C, D)]
costs = [[2**64 for _ in range(Max + 1)] for _ in range(N)]
que = [(0, 0, S)]
while que:
	(cost_sum, node, coins) = heappop(que)
	for to, pay, cost in graph[node]:
		if coins >= pay and cost_sum + cost < costs[to][min(Max, coins - pay)]:
			costs[to][min(Max, coins - pay)] = cost_sum + cost
			heappush(que, (cost_sum + cost, to, min(Max, coins - pay)))
for i in range(1, N):
	print(min(costs[i]))

Solution (Python):
ic=lambda i,c:i+c*50
n,m,s=map(int,input().split())
edge=[[]for _ in range(125100)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  for i in range(a,2501):
    edge[ic(u,i)].append((ic(v,i-a),b))
    edge[ic(v,i)].append((ic(u,i-a),b))
for i in range(n):
  c,d=map(int,input().split())
  for j in range(c,2501):
    edge[ic(i,j-c)].append((ic(i,j),d))
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
d=dijkstra(ic(0,min(2500,s)),125100,edge)
ans=[0]+[10**20]*(n-1)
for i in range(1,n):
  for j in range(2501):ans[i]=min(ans[i],d[ic(i,j)])
print(*ans[1:])

Solution (Python):
import heapq
inf = 10**20
h = 2500
n, m, s = map(int, input().split())
s = min(h-1, s)

A = [[inf for j in range(n)] for i in range(n)]

B = [[inf for j in range(n)] for i in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    A[u-1][v-1] = a
    A[v-1][u-1] = a
    B[u-1][v-1] = b
    B[v-1][u-1] = b
CD = [tuple(map(int, input().split())) for i in range(n)]
C = [c for c, d in CD]
D = [d for c, d in CD]

G = {(i, x): {} for i in range(n) for x in range(h)}
for i in range(n):
    for j in range(n):
        for x in range(h):
            if i == j:
                G[i, x][i, x] = 0
                if x-1 >= 0:
                    G[i, x][i, x-1] = 0
                if x+C[i] < h:
                    G[i, x][i, x+C[i]] = D[i]
            elif x >= A[i][j]:
                G[i, x][j, x-A[i][j]] = B[i][j]

T = {(i, x): inf for i in range(n) for x in range(h)}
T[0, s] = 0
Q = [(0, (0, s))]
heapq.heapify(Q)
while Q:
    _, (i, x) = heapq.heappop(Q)
    for j, y in G[i, x].keys():
        if T[i, x]+G[i, x][j, y] < T[j, y]:
            T[j, y] = T[i, x] + G[i, x][j, y]
            heapq.heappush(Q, (T[j, y], (j, y)))
for i in range(1, n):
    print(T[i, 0])

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

def solve():
    input = sys.stdin.readline
    N, M, S = map(int, input().split())
    Edge = [[] for _ in range(N)] 
    maxCost = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        Edge[u-1].append((b, v-1, a))
        Edge[v-1].append((b, u-1, a))
        maxCost = max(a, maxCost)
    exchange = [None] * N 
    for i in range(N): exchange[i] = [int(c) for c in input().split()]
    maxCost *= N

    minTime = [[10 ** 20 for _ in range(maxCost + 1)] for i in range(N)]
    q = []
    heapify(q)
    heappush(q, (0, 0, S)) 
    while q:
        cT, cN, cM = heappop(q)
        if minTime[cN][min(maxCost, cM)] == 10 ** 20:
            minTime[cN][min(maxCost, cM)] = cT
            if cM < maxCost: heappush(q, (cT + exchange[cN][1], cN, cM + exchange[cN][0]))
            for addTime, nextNode, payCost in Edge[cN]:
                if cM >= payCost: heappush(q, (cT + addTime, nextNode, cM - payCost))
    
    for i in range(1, N): print(min(minTime[i]))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""


def main():
    n, m, s = map(int, input().split())
    edge = [[] for i in range(n)]
    cl, dl = [None]*n, [None]*n
    sa = 0
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append((v, b, a))
        edge[v].append((u, b, a))
        sa += a
    for i in range(n):
        c, d = map(int, input().split())
        cl[i] = c
        dl[i] = d
    dijkstra(n, s, edge, cl, dl)
        
        
    
def dijkstra(n, coin, edges, cl, dl):
    coin_max = 5000
    start = 0
    coin = min(coin, coin_max)
    d = [[10**15]*(coin_max+1) for _ in range(n)]
    d[start][coin] = 0
    priority_queue = []
    heappush(priority_queue, (0, start, coin))
    while priority_queue:
        cost_i, i, coin_i = heappop(priority_queue)
        if d[i][coin_i] < cost_i:
            continue
        supplied_coin = coin_i + cl[i]
        if supplied_coin <= coin_max and cost_i + dl[i] < d[i][supplied_coin]:
            d[i][supplied_coin] = cost_i + dl[i]
            heappush(priority_queue, (cost_i + dl[i], i, supplied_coin))
        for _to, _cost, _coin in edges[i]:
            ci = coin_i-_coin
            if coin_i >= _coin and d[_to][ci] > cost_i + _cost:
                d[_to][ci] = cost_i + _cost
                heappush(priority_queue, (cost_i + _cost, _to, ci))
    for i in d[1:]:
        print(min(i))
    
        

if __name__ == "__main__":
    main()