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.



Sample input:
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5


Sample output:
2
14

Submission status: Runtime Error

Solution code:
import sys, heapq
import numpy as np

input = sys.stdin.readline
N, M, S = map(int, input().split())
# b, dふん
# a, c, 金
UVABs = np.array([tuple(map(int, input().split())) for _ in range(M)], dtype=int)
CDs = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype=int)
pathes = [{} for _ in range(N+1)]
for u, v, a, b in UVABs:
    pathes[u][v] = (a, b)
    pathes[v][u] = (a, b)
max_coin = np.max(UVABs[:, 2])*N
h = [(0, 1, S)] # time, town, coin
mins = np.ones((N, max_coin+1))*np.inf

heapq.heapify(h)
while len(h)>0:
    time, town, coin = heapq.heappop(h)
    if mins[town-1, coin] < time:
        continue
    mins[town-1, coin] = time
    c, d = CDs[town-1]
    for i in range(1, (max_coin+1-coin)//c):
        if mins[town-1, coin+i*c] < time+i*d:
            continue
        mins[town-1, coin+i*c] = time + i * d
        heapq.heappush(h, (time+i*d, town, coin+i*c))
    for next_town, (a, b) in pathes[town].items():
        if coin < a:
            continue
        if mins[next_town-1, coin-a] < time+b:
            continue
        mins[next_town-1, coin-a] = time+b
        heapq.heappush(h, (time+b, next_town, coin-a))

print(' '.join(map(lambda x: str(int(x)), np.min(mins, axis=1)[1:])))

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
x=51
r=range(0,x**3,x)
for u,v,a,b in t[:m]:
 for i in r:D+=i+a*x+u,i+v,b,i+a*x+v,i+u,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:D+=j+i,j+c*x+i,d
d=csgraph.dijkstra(csr_matrix((D[2::3],(D[::3],D[1::3]))),1,min(j,s*x)+1)
for i in range(2,n+1):print(int(min(d[i::x])))

Submission status: Runtime Error

Solution code:

from heapq import heappush, heappop
def resolve():
    INF = float('inf')
    maxMoney = 2502

    def Dijkstra(g):
        ans = {}
        # ある頂点にいて、ある銀貨の枚数を持っているときのこれまでにかかった最短時間
        dp = [[INF] * (maxMoney + 1) for _ in range(N)]
        # (time, node, silver)
        hq = []
        heappush(hq, (0, 0, min(S, maxMoney)))
        while hq:
            t, v, s = heappop(hq)
            if t > dp[v][s]:
                continue
            if v not in ans:
                ans[v] = t
                if len(ans) == N:
                    break

            # buy
            if s < maxMoney:
                c, d = CD[v]
                new_s = min(s + c, maxMoney)
                new_t = t + d
                if new_t < dp[v][new_s]:
                    dp[v][new_s] = new_t
                    heappush(hq, (new_t, v, new_s))

            # move
            for nv, cost, time in G[v]:
                # 払えない
                if s < cost:
                    continue
                # 払って移動した場合、最短時間なら更新
                new_s = s - cost
                new_t = t + time
                if new_t < dp[nv][new_s]:
                    dp[nv][new_s] = new_t
                    heappush(hq, (new_t, nv, new_s))
        return ans

    N, M, S = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v, coin, tm = map(int, input().split())
        u, v = u - 1, v - 1
        G[u].append((v, coin, tm))
        G[v].append((u, coin, tm))
    CD = [list(map(int, input().split())) for _ in range(N)]

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


if __name__ == "__main__":
    resolve(

Submission status: Runtime Error

Solution code:
import heapq

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

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

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

for k in range(s+1):
    time[1][k]=0

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

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

Submission status: Runtime Error

Solution code:
n,m,s=map(int,input().split())
path=[[] for _ in range(n+1)]
coin=[(0,0)]
time=[float("inf") for _ in range(n+1)]
time[0]=0
queue=[]
for i in range(m):
    u,v,a,b=map(int,input().split())
    path[u].append((v,a,b))
    path[v].append((u,a,b))

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

heapq.heappush(queue,(0,s,1))
while len(queue)!=0:
    t,c,v=heapq.heappop(queue)
    if max(time)<t:
        continue

    if time[v]>t:
        time[v]=t

    for nv,na,nb in path[v]:
        if na>c:
            continue
        else:
            heapq.heappush(queue,(t+nb,c-na,nv))
    heapq.heappush(queue,(t+coin[v][1],c+coin[v][0],v))
    
print(*time[2:],sep="\n")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**9

MAX_SILVER = 3000 

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

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

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

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

DIJK = Dijkstra(edge)
dist = DIJK.calc(s)

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

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
N, M, S = map(int, input().split())
edge = [[] for _ in range(N)]
for i 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))

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

# キューの中身(時間,銀貨の数,現在地)
q = [(0, S, 0)]
d = [[-1] * 5010 for _ in range(N)]
#d[0][S] = 0
while len(q) > 0:
    t, s, v = heappop(q)
    if d[v][s] > -1: continue
    d[v][s] = t
    for nv, ns, nt in edge[v]:
        if s < ns: continue
        heappush(q, (t+nt, s-ns, nv))
    c, dtime = CD[v]
    if s+c <= 5000:
        heappush(q, (t+dtime, s+c, v))

INF = 10 ** 30
for j in range(1, N):
    print(min([i if i > -1 else INF for i in d[j]]))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

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

# 銀貨を何枚持っているかの状態数、N*2501の都市, dijkstra
N, M, S = lr()
limit = 2500
graph = [[] for _ in range((N+1) * (limit+1))]  # 1-indexed
for _ in range(M):
    u, v, a, b = lr()
    for x in range(a, limit+1):
        graph[u*(limit+1) + x].append(((v*(limit+1)+x-a), b))
        graph[v*(limit+1) + x].append(((u*(limit+1)+x-a), b))

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

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

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

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush

def main():
    N,M,S=map(int,input().split())
    G=[[] for _ in range(N)]
    for i in range(M):
        U,V,A,B=map(int,input().split())
        G[U-1].append([V-1,A,B])
        G[V-1].append([U-1,A,B])
    C=[]
    D=[]
    for _ in range(N):
        c,d=map(int,input().split())
        C.append(c)
        D.append(d)

    MaxMoney=2500

    dp=[[float('inf') for __ in range(MaxMoney+1)] for _ in range(N)]

    cost=0
    money=S
    que=[]
    heappush(que,(cost,0,money)) #cost,node,money
    dp[0][money] = 0

    while len(que)>0:
        cost,node,money=heappop(que)

        stop_money=min(money+C[node],MaxMoney)
        stop_cost=cost+D[node]
        if stop_cost<dp[node][stop_money]:
            dp[node][stop_money]=stop_cost
            heappush(que,(stop_cost,node,stop_money))

        for to_node,to_money,to_cost in G[node]:
            money_=min(money-to_money,MaxMoney)
            if money_<0:
                continue
            cost_=cost+to_cost
            if dp[to_node][money_]<=cost_:
                continue

            dp[to_node][money_]=cost_
            heappush(que,(cost_,to_node,money_))

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




if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  dp=[[inf]*(50*50+1)for _ in range(n)]
  kakutei=[[0]*(50*50+1)for _ in range(n)]
  dp[0][min(s,50*50)]=0
  todo=[[0,0,min(s,50*50)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(100*51-1,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  dp=[[inf]*(50*50)for _ in range(n)]
  kakutei=[[0]*(50*50)for _ in range(n)]
  dp[0][min(s,50*50-1)]=0
  todo=[[0,0,min(s,50*50-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(100*51-1,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
  import heapq,math
  dp=[[math.inf]*(100*51)for _ in range(n)]
  kakutei=[[0]*(100*51)for _ in range(n)]
  dp[0][min(s,100*51-1)]=0
  todo=[[0,0,min(s,100*51-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[math.inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    if kakutei[v][i+a]==0:
      j=min(100*51-1,i+c)
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

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

A_max=max([a for _,_,a,_ in E])

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        to_state_v=(v,from_a-a)
        from_state_u=(u,from_a)
        D[from_state_u].append((b,to_state_v))
        to_state_u=(u,from_a-a)
        from_state_v=(v,from_a)
        D[from_state_v].append((b,to_state_u))

for c,d in C:
    for n in range(N):
        for a in range(A_max+1):
            if a+c>A_max:
                continue
            to_state=(n,a+c)
            from_state=(n,a)
            D[from_state].append((d,to_state))


start=(0,max(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

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

A_max=max([a for _,_,a,_ in E])

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(a,A_max+1):
        state=(v,from_a-a)
        D[(u,from_a)].append((b,state))

for c,d in C:
    for i in range(N):
        if i+c>A_max:
            continue
        state=(u,i+c)
        D[(u,i)].append((d,state))


start=(0,max(A_max,S))
Q=[(0,state)]

Dist=defaultdict(lambda :float('inf'))

Dist[state]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)

Submission status: Runtime Error

Solution code:
import heapq


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    INF = 10**9

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], self.INF) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

    s_max = 2500
    S = min(S, s_max)

    dik = Dijkstra()
    edge = dict()
    s0 = (1, S)

    for m in range(1, M + 1):
        U, V, A, B = map(int, input().split())
        for s in range(A, s_max + 1):
            if not (U, s) in edge:
                edge[(U, s)] = []
            if not (V, s) in edge:
                edge[(V, s)] = []
            edge[(U, s)].append([B, (V, s - A)])
            edge[(V, s)].append([B, (U, s - A)])

    for n in range(1, N + 1):
        C, D = map(int, input().split())
        for s in range(s_max + 1):
            s1 = min(s + C, s_max)
            if not (n, s) in edge:
                edge[(n, s)] = []
            edge[(n, s)].append([D, (n, s1)])

    d = dik(s0, edge)

    for n in range(2, N + 1):
        ans = Dijkstra.INF
        for s in range(s_max + 1):
            ans = min(ans, d.get((n, s)), Dijkstra.INF)
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import heapq

INF = 10**7


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], INF) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

s_max = 2500
S = min(S, s_max)

dik = Dijkstra()
edge = dict()
s0 = (1, S)

for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        if not (U, s) in edge:
            edge[(U, s)] = []
        if not (V, s) in edge:
            edge[(V, s)] = []
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        if not (n, s) in edge:
            edge[(n, s)] = []
        edge[(n, s)].append([D, (n, s1)])

d = dik(s0, edge)

for n in range(2, N + 1):
    ans = INF
    for s in range(s_max + 1):
        ans = min(ans, d.get((n, s)), INF)
    print(ans)

Submission status: Runtime Error

Solution code:
import heapq

INF = 10 ** 9


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], INF) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

s_max = 2500
S = min(S, s_max)

dik = Dijkstra()
edge = dict()
s0 = (1, S)

for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        if not (U, s) in edge:
            edge[(U, s)] = []
        if not (V, s) in edge:
            edge[(V, s)] = []
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        if not (n, s) in edge:
            edge[(n, s)] = []
        edge[(n, s)].append([D, (n, s1)])

d = dik(s0, edge)

for n in range(2, N + 1):
    ans = INF
    for s in range(s_max + 1):
        ans = min(ans, d.get((n, s)), INF)
    print(ans)

Submission status: Runtime Error

Solution code:
import heapq

INF = 10 ** 9


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], INF) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

    s_max = 2500
    S = min(S, s_max)

    dik = Dijkstra()
    edge = dict()
    s0 = (1, S)

    for m in range(1, M + 1):
        U, V, A, B = map(int, input().split())
        for s in range(A, s_max + 1):
            if not (U, s) in edge:
                edge[(U, s)] = []
            if not (V, s) in edge:
                edge[(V, s)] = []
            edge[(U, s)].append([B, (V, s - A)])
            edge[(V, s)].append([B, (U, s - A)])

    for n in range(1, N + 1):
        C, D = map(int, input().split())
        for s in range(s_max + 1):
            s1 = min(s + C, s_max)
            if not (n, s) in edge:
                edge[(n, s)] = []
            edge[(n, s)].append([D, (n, s1)])

    d = dik(s0, edge)

    for n in range(2, N + 1):
        ans = INF
        for s in range(s_max + 1):
            ans = min(ans, d.get((n, s)), INF)
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import heapq

INF = 10**9


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], INF) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

s_max = 2500
S = min(S, s_max)

dik = Dijkstra()
edge = dict()
s0 = (1, S)

for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        if not (U, s) in edge:
            edge[(U, s)] = []
        if not (V, s) in edge:
            edge[(V, s)] = []
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        if not (n, s) in edge:
            edge[(n, s)] = []
        edge[(n, s)].append([D, (n, s1)])

d = dik(s0, edge)

for n in range(2, N + 1):
    ans = INF
    for s in range(s_max + 1):
        ans = min(ans, d.get((n, s)), INF)
    print(ans)