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 *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**16
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*3005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,3000),0))
    dp[0][min(s,3000)]=0

    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        c,d=cd[u]
        if g+c<3000:
            if dp[u][g + c] > t + d:
                dp[u][g + c] = t + d
                heappush(hp, (t + d, g + c, u))
        else:
            if dp[u][3000] > t + d:
                dp[u][3000] = t + d
                heappush(hp, (t + d, 3000, u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()

Solution (Python):
from heapq import heappush, heappop
inf = float('inf')
def dijkstra(graph:list, node:int, start:int) -> list:
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

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

for i in range(N):
    c,d = map(int,input().split())
    for s in range(2500):
        graph[2501*i+s].append([d,2501*i+min(2500,s+c)])

dist = dijkstra(graph,2501*N,min(2500,S))

ans = [inf]*N
for i in range(N):
    for s in range(2501):
        ans[i] = min(ans[i],dist[2501*i+s])

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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n, m, s = LI()
    uvab = LIR(m)
    cd = LIR(n)
    dp = [[inf] * 2501 for i in range(n)]
    edg = [[] for i in range(n)]
    for u, v, a, b in uvab:
        edg[u - 1].append((v - 1, a, b))
        edg[v - 1].append((u - 1, a, b))
    for i, (c, d) in enumerate(cd):
        edg[i].append((i, -c, d))
    if s >= 2501:
        s = 2500
    q = [(0, 0, s)]
    dp[0][s] = 0
    time = 0
    while q:
        time, p, score = heappop(q)
        for e, a, b in edg[p]:
            timebuf = time
            if 0 <= score - a <= 2500:
                timebuf += b
                if dp[e][score - a] > timebuf:
                    dp[e][score - a] = timebuf
                    heappush(q, (timebuf, e, score - a))
                    for i in range(score - a, -1, -1):
                        if dp[e][i] > timebuf:
                            dp[e][i] = timebuf
                        else:
                            break
    
    for i in range(1, n):
        print(min(dp[i]))

    return



if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque

N,M,S = map(int,input().split())
city = [[]for i in range(N)]
for i in range(M):
    u,v,a,b = map(int,input().split())
    city[u-1].append([v-1,a,b])
    city[v-1].append([u-1,a,b])
ex = [[] for i in range(N)]
for i in range(N):
    c,d = map(int,input().split())
    ex[i] = [c,d]

MCOIN = 5000

cost = [[float('inf')]*(MCOIN+500) for i in range(N)]
cost[0][min(MCOIN,S)] = 0

queue = deque([[0,min(MCOIN,S)]])
while queue:
    p,m = queue.popleft()
    if m < MCOIN and cost[p][m+ex[p][0]] > cost[p][m] + ex[p][1]:
        queue.append([p,m+ex[p][0]])
        cost[p][m+ex[p][0]] = cost[p][m] + ex[p][1]
    for v,a,b in city[p]:
        if m >= a  and cost[v][m-a] > cost[p][m] + b:
            queue.append([v,m-a])
            cost[v][m-a] = cost[p][m] + b

for i in cost[1:]:
    print(min(i))

Solution (Python):
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0

dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    sc = min(s + c, 50 * N + 10)
    if d + dd < dp[v, sc]:
        dp[v, sc] = d + dd
        heapq.heappush(heap, (d + dd, v, sc))

print(*ans[2:], sep='\n')

Solution (Python):
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] 
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

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

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*(50*(N-1)+1))
for i in range(0,M):
    u,v,a,b=map(int,input().split())
    for j in range(a,50*(N-1)+1):
        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,50*(N-1)):
        to=min(50*(N-1),j+c)
        pro.add(N*j+i,N*to+i,d)

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

Solution (Python):
def main():
    import heapq
    inf = 10**16
    n, m, s = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*n]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c, d]) for a, b, c, d in uvab]
    [g[b-1].append([a-1, c, d]) for a, b, c, d in uvab]
    vertex = [[inf]*2501 for _ in [0]*n]
    h = [(0, 0, min(s, 2500))]  
    heapq.heapify(h)
    while h:
        t, p, money = heapq.heappop(h)
        if vertex[p][money] != inf:
            continue
        vertex[p][money] = t
        newmoney = min(money+cd[p][0], 2500)
        if vertex[p][newmoney] == inf:
            heapq.heappush(h, (t+cd[p][1], p, newmoney))
        for a, b, c in g[p]:  
            if money < b:
                continue
            if vertex[a][money-b] != inf:
                continue
            heapq.heappush(h, (t+c, a, money-b))
    for i in vertex[1:]:
        print(min(i))


main()

Solution (Python):
n,m,s = map(int,input().split())
road = [[] for _ in range(n)]

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

coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18

arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]


for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}

for _ in range(50):
  
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])

Solution (Python):
import heapq

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

E = [[] for _ in range(N)]
A = [[0]*N for _ in range(N)]
B = [[0]*N for _ in range(N)]
for i in range(M):
    U, V, a, b = map(int, input().split())
    u = U-1
    v = V-1
    E[u].append(v)
    E[v].append(u)
    A[u][v] = A[v][u] = a
    B[u][v] = B[v][u] = b

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

M = 50*N
T = [[-1]*M for _ in range(N)]
h = []
heapq.heappush(h, (0, 0, min(M-1, S))) 
while h:
    dmin, inode, snode = heapq.heappop(h)
    if T[inode][snode]!=-1: continue
    T[inode][snode] = dmin

    
    for enode in E[inode]:
        a = A[inode][enode]
        b = B[inode][enode]
        esnode = snode-a
        if esnode<0 or T[enode][esnode]!=-1: continue
        heapq.heappush(h, (dmin+b, enode, esnode))

    
    c = C[inode]
    d = D[inode]
    snode_c = min(M-1, snode+c)
    if T[inode][snode_c]!=-1: continue
    heapq.heappush(h, (dmin+d, inode, snode_c))

for inode in range(1, N):
    print(min([x for x in T[inode] if x>=0]))

Solution (Python):
n,m,s = map(int,input().split())
road = [[] for _ in range(n)]

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

coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18

arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]


for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}

for _ in range(100):
  
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])

Solution (Python):
import heapq
inf = 10**18
def dijkstra(s, n, G):
    dist = [inf]*n
    edges = []
    dist[s] = 0
    for e in G[s]:
        heapq.heappush(edges, e)
    while edges:
        cost, v = heapq.heappop(edges)
        if dist[v] != inf:
            continue
        dist[v] = cost
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv))
    return dist
mx = 5005
n, m, s = map(int, input().split())
g = [[] for _ in range(n*mx)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u-=1
    v-=1
    for j in range(mx):
        if j>=a:
            g[u*mx+j].append((b, v*mx+j-a))
            g[v*mx+j].append((b, u*mx+j-a))
for i in range(n):
    c, d = map(int, input().split())
    for j in range(mx-c):
        g[i*mx+j].append((d, i*mx+j+c))
dist = dijkstra(min(s, mx-1), len(g), g)
for i in range(1, n):
    res = inf
    for j in range(mx):
        res = min(res, dist[i*mx+j])
    print(res)

Solution (Python):
import heapq
from collections import defaultdict
import sys

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

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

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

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

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

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

Solution (Python):
n, m, s = [int(i) for i in input().split()]

e = []
for _ in range(m):
    u, v, a, b = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    e.append([u, v, a, b])

co = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[10 ** 18] * 6000 for _ in range(n)]
dp[0][min(5999,s)] = 0
for i in range(6000):
    if i + co[0][0] < 6000:
        dp[0][i + co[0][0]] = min(dp[0][i + co[0][0]], dp[0][i] + co[0][1])

for _ in range(n):
    for u, v, a, b in e:
        for j in range(a, 6000):
            dp[v][j - a] = min(dp[v][j - a], dp[u][j] + b)
        for i in range(6000):
            if i + co[v][0] < 6000:
                dp[v][i + co[v][0]] = min(dp[v][i + co[v][0]], dp[v][i] + co[v][1])

        for j in range(a, 6000):
            dp[u][j - a] = min(dp[u][j - a], dp[v][j] + b)
        for i in range(6000):
            if i + co[u][0] < 6000:
                dp[u][i + co[u][0]] = min(dp[u]
                                          [i + co[u][0]], dp[u][i] + co[u][1])

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

Solution (Python):
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


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

MAX_SILVER = 5005
n2 = MAX_SILVER * n
graph = [[] for _ in range(n2)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for k in range(a, MAX_SILVER):
        graph[u * MAX_SILVER + k].append((b, v * MAX_SILVER + k - a))
        graph[v * MAX_SILVER + k].append((b, u * MAX_SILVER + k - a))
for i in range(n):
    c, d = map(int, input().split())
    for k in range(MAX_SILVER - 1):
        graph[i * MAX_SILVER + k].append(
            (d, i * MAX_SILVER + min(k + c, MAX_SILVER - 1)))

dist = dijkstra(graph, n2, 0 + min(s, MAX_SILVER - 1))

for i in range(1, n):
    ans_i = 10**20
    for k in range(MAX_SILVER):
        ans_i = min(ans_i, dist[i * MAX_SILVER + k])
    print(ans_i)

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

INF = float('inf')  
maxMoney = 2502  


N, M, S = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
    u, v, coin, tm = map(int, input().split())
    u, v = u-1, v-1
    adjL[u].append((v, coin, tm))
    adjL[v].append((u, coin, tm))
moneys, tms = [], []
for _ in range(N):
    money, tm = map(int, input().split())
    moneys.append(money)
    tms.append(tm)


def Dijkstra(adjList):
    numV = N * (maxMoney+1)
    numUsed = 0
    costss = [[INF]*(maxMoney+1) for _ in range(N)]
    costss[0][S] = 0
    PQ = []
    heappush(PQ, (0, 0, S))
    while PQ:
        cNow, vNow, moneyNow = heappop(PQ)
        if cNow > costss[vNow][moneyNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, coin, tm in adjList[vNow]:
            if moneyNow < coin: continue
            c2 = cNow + tm
            m2 = moneyNow - coin
            if c2 < costss[v2][m2]:
                costss[v2][m2] = c2
                heappush(PQ, (c2, v2, m2))
        c2 = cNow + tms[vNow]
        m2 = moneyNow + moneys[vNow]
        if m2 > maxMoney:
            m2 = maxMoney
        if c2 < costss[vNow][m2]:
            costss[vNow][m2] = c2
            heappush(PQ, (c2, vNow, m2))
    return costss

S = min(S, maxMoney)
costss = Dijkstra(adjL)



anss = [min(costss[t]) for t in range(1, N)]
print('\n'.join(map(str, anss)))

Solution (Python):
import sys, heapq
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	
	
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

INF = 10**20
n, m, s = map(int, input().split())
s = min(s, m*50)
adj = [[] for _ in range(n*(m+1)*50)]

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

for i in range(n):
	c, d = map(int, input().split())
	for j in range(m*50):
		adj[j * n + i].append((min(m*50, j + c) * n + i, d))

dijk = DijkstraList(adj, s*n)
dijk.solve()
ans = [INF for _ in range(n)]
for num, x in enumerate(dijk.dist):
	i = num%n
	ans[i] = min(ans[i], x)
print(*ans[1:], sep="\n")

Solution (Python):
from queue import PriorityQueue
from collections import defaultdict
from heapq import heappush, heappop

n, m, s = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u][v] = (a, b)
    graph[v][u] = (a, b)

town = [None]*(n+1)
for i in range(n):
    c, d = map(int, input().split())
    town[i+1] = (c, d)

if s >= 2501:
    s = 2501
x = (1, s)
cost = 0
visit = set()
heap = []
heappush(heap, (cost, x))
ans = [None]*(n+1)
check = 0
while len(heap) > 0:
    cost, x = heappop(heap)
    if x in visit:
        continue
    visit.add(x)
    p, m = x
    if ans[p] is None:
        ans[p] = cost
        check += 1
        if check >= n:
            break
    c, d = town[p]
    if m <= 2501:
        heappush(heap, (cost+d, (p, m+c)))
    for q, edge in graph[p].items():
        a, b = edge
        if m-a >= 0:
            heappush(heap, (cost+b, (q, m-a)))
for i in range(2, n+1):
    print(ans[i])

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

class Graph():  
    def __init__(self, n, edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append((e[1], e[2]))
            self.deg[e[1]] += 1

    def dijkstra(self, s, INF=10**18):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    heappush(heap, (dist[adj], adj))
        return dist

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

node = [[0 for j in range(2500)] for i in range(N)]
E = []

for i in range(M):
    u, v, a, b = T[i]
    u -= 1
    v -= 1
    for c in range(2500):
        if c - a >= 0:
            E.append((2500 * u + c, 2500 * v + c - a, b))
            E.append((2500 * v + c, 2500 * u + c - a, b))

for i in range(N):
    a, b = C[i]
    for c in range(2500):
        if c + a < 2500:
            E.append((2500 * i + c, 2500 * i + c + a, b))
        else:
            E.append((2500 * i + c, 2500 * i + 2499, b))

G = Graph(2500 * N, E)
D = G.dijkstra(min(2499, S))

for i in range(N):
    if i == 0:
        continue
    res = 10**18
    for j in range(2500):
        res = min(res, D[i * 2500 + j])
    print(res)

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

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()