Problem:
 Score : 500 points    Problem Statement  There are N cities numbered 1 to N , connected by M railroads.  You are now at City 1 , with 10^{100} gold coins and S silver coins in your pocket.  The i -th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes.
You cannot use gold coins to pay the fare.  There is an exchange counter in each city. At the exchange counter in City i , you can get C_i silver coins for 1 gold coin.
The transaction takes D_i minutes for each gold coin you give.
You can exchange any number of gold coins at each exchange counter.  For each t=2, ..., N , find the minimum time needed to travel from City 1 to City t . You can ignore the time spent waiting for trains.      Constraints   2 \leq N \leq 50  N-1 \leq M \leq 100  0 \leq S \leq 10^9  1 \leq A_i \leq 50  1 \leq B_i,C_i,D_i \leq 10^9  1 \leq U_i < V_i \leq N  There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j) .  Each city t=2,...,N can be reached from City 1 with some number of railroads.  All values in input are integers.         Input  Input is given from Standard Input in the following format:  N  M  S  U_1  V_1  A_1  B_1  :  U_M  V_M  A_M  B_M  C_1  D_1  :  C_N  D_N       Output  For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t .        Sample Input 1 3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5      Sample Output 1 2
14  The railway network in this input is shown in the figure below.  In this figure, each city is labeled as follows:   The first line: the ID number i of the city ( i for City i )  The second line: C_i / D_i   Similarly, each railroad is labeled as follows:   The first line: the ID number i of the railroad ( i for the i -th railroad in input)  The second line: A_i / B_i    You can travel from City 1 to City 2 in 2 minutes, as follows:   Use the 1 -st railroad to move from City 1 to City 2 in 2 minutes.    You can travel from City 1 to City 3 in 14 minutes, as follows:   Use the 1 -st railroad to move from City 1 to City 2 in 2 minutes.  At the exchange counter in City 2 , exchange 3 gold coins for 3 silver coins in 6 minutes.  Use the 1 -st railroad to move from City 2 to City 1 in 2 minutes.  Use the 2 -nd railroad to move from City 1 to City 3 in 4 minutes.        Sample Input 2 4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4      Sample Output 2 5
5
7  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 4 in 7 minutes, as follows:   At the exchange counter in City 1 , exchange 2 gold coins for 6 silver coins in 2 minutes.  Use the 2 -nd railroad to move from City 1 to City 3 in 4 minutes.  Use the 4 -th railroad to move from City 3 to City 4 in 1 minutes.        Sample Input 3 6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1      Sample Output 3 1
9003
14606
16510
16576  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 6 in 16576 minutes, as follows:   Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.  At the exchange counter in City 2 , exchange 3 gold coins for 3 silver coins in 9000 minutes.  Use the 1 -st railroad to move from City 2 to City 1 in 1 minute.  Use the 2 -nd railroad to move from City 1 to City 3 in 1 minute.  At the exchange counter in City 3 , exchange 8 gold coins for 8 silver coins in 5600 minutes.  Use the 2 -nd railroad to move from City 3 to City 1 in 1 minute.  Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.  Use the 3 -rd railroad to move from City 2 to City 4 in 1 minute.  At the exchange counter in City 4 , exchange 19 gold coins for 19 silver coins in 1900 minutes.  Use the 3 -rd railroad to move from City 4 to City 2 in 1 minute.  Use the 1 -st railroad to move from City 2 to City 1 in 1 minute.  Use the 2 -nd railroad to move from City 1 to City 3 in 1 minute.  Use the 4 -th railroad to move from City 3 to City 5 in 1 minute.  At the exchange counter in City 5 , exchange 63 gold coins for 63 silver coins in 63 minutes.  Use the 4 -th railroad to move from City 5 to City 3 in 1 minute.  Use the 2 -nd railroad to move from City 3 to City 1 in 1 minute.  Use the 5 -th railroad to move from City 1 to City 6 in 1 minute.        Sample Input 4 4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7      Sample Output 4 1
3
5  The railway network in this input is shown in the figure below:        Sample Input 5 2 1 0
1 2 1 1
1 1000000000
1 1      Sample Output 5 1000000001  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 2 in 1000000001 minutes, as follows:   At the exchange counter in City 1 , exchange 1 gold coin for 1 silver coin in 1000000000 minutes.  Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.

Solution (Python):
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


n,m,s=LI()
t_ls=[]
k=1+n*50
s=min(k-1,s)
for i in range(m):
    u,v,a,b=LI()
    u-=1
    v-=1
    for j in range(a,k):
        t_ls+=[(u*k+j,v*k+j-a,b)]
        t_ls+=[(v*k+j,u*k+j-a,b)]

for i in range(n):
    c,d=LI()
    for j in range(k):
        t_ls+=[(i*k+j,i*k+min(j+c,k-1),d)]

gt,_=GI(n*k,len(t_ls),ls=t_ls,Directed=True,index=0)
dist_t,_=dijkstra(gt,0*k+s)

for i in range(1,n):
    print(min(dist_t[i*k:-~i*k]))

Solution (Python):
import heapq

n, m, s = [int(x) for x in input().split()]
adj = [[] for u in range(n + 1)]
for e in range(m):
    u, v, a, b = [int(x) for x in input().split()]
    adj[u].append((v, a, b))
    adj[v].append((u, a, b))
exchange = [[int(x) for x in input().split()] if u else [] for u in range(n + 1)]
def bound(s):
    return min(s, n * 50)
pq, done, d = [(0, 1, bound(s))], set(), {(1, bound(s)): 0}
ans = [float('inf') for u in range(n + 1)]
while len(pq) > 0:
    dist, u, s = heapq.heappop(pq)
    ans[u] = min(ans[u], dist)
    if (u, s) not in done:
        for v, a, b in adj[u]:
            if s >= a and d.get((v, bound(s - a)), float('inf')) > d[u, s] + b:
                d[v, bound(s - a)] = d[u, s] + b
                heapq.heappush(pq, (d[v, bound(s - a)], v, bound(s - a)))
        c, t = exchange[u]
        if d.get((u, bound(s + c)), float('inf')) > d[u, s] + t:
            d[u, bound(s + c)] = d[u, s] + t
            heapq.heappush(pq, (d[u, bound(s + c)], u, bound(s + c)))
        done.add((u, s))

print(*(ans[u] for u in range(2, n + 1)), sep='\n')

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

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)

'''
from itertools import combinations 
N = 14
M = N*(N-1)//2
S = 0
UVAB = [[x,y,50,10**9] for x,y in combinations(range(1,N+1),2)] 
U,V,A,B = zip(*UVAB)
'''

mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))

CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]

C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] <= t:
        continue
    for i in range(w+1):
        ans[v][i] = min(t, ans[v][i])
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

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

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

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
from collections import defaultdict
from collections import deque
import heapq


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, s, t, w=1):
        self.E[s].append((t, w))
        


def shortestPath(g: Graph, s: int):
    
    
    
    dist = defaultdict(lambda: INF)
    dist[s] = 0

    prev = defaultdict(lambda: None)
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, S: int,
          U: "List[int]", V: "List[int]",
          A: "List[int]", B: "List[int]",
          C: "List[int]", D: "List[int]"):

    
    
    NN = 50*N*N
    g = Graph(NN)
    
    
    
    for i in range(M):
        for j in range(50*N):
            if j - A[i] < 0:
                continue
            g.add_edge((U[i]-1, j), (V[i]-1, j-A[i]), B[i])
            g.add_edge((V[i]-1, j), (U[i]-1, j-A[i]), B[i])
        
    
    for i in range(N):
        for j in range(50*N):
            if j-C[i] >= 0:
                g.add_edge((i, j-C[i]), (i, j), D[i])

    if S >= (N-1)*50:
        S = (N-1)*50
    dist, prev = shortestPath(g, (0, S))
    

    
    for n in range(1, N):
        tot = INF
        for i in range(50*N):
            if (n, i) in dist:
                tot = min(tot, dist[n, i])
                
        print(tot)
        
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    S = int(next(tokens))  
    U = [int()] * (M)  
    V = [int()] * (M)  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  
    D = [int()] * (N)  
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, S, U, V, A, B, C, D)


if __name__ == '__main__':
    main()

Solution (Python):
N,M,S = map(int,input().split())
edges = [[] for _ in range(2500*50 + 100)]
def indexer(city,coin):
    return 50*coin + city

for _ in range(M):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    for scoin in range(a,2501):
        edges[indexer(u,scoin)].append((b,indexer(v,scoin-a)))
        edges[indexer(v,scoin)].append((b,indexer(u,scoin-a)))

for i in range(N):
    c,d = map(int,input().split())
    for scoin in range(c,2501):
        edges[indexer(i,scoin-c)].append((d,indexer(i,scoin)))

def dijkstra(s,n,edges):
    import heapq
    INF = float('inf')
    d = [INF]*n
    d[s] = 0
    pq = [(0,s)]
    while len(pq):
        c,v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for v2nvcost, nv in edges[v]:
            if c + v2nvcost < d[nv]:
                d[nv] = c + v2nvcost
                heapq.heappush(pq,(d[nv],nv))
    return d


d=dijkstra(indexer(0,min(2500,S)),2500*50 + 100,edges)
for i in range(1,N):
    ans = float('inf')
    for j in range(2501):
        ans = min(ans,d[indexer(i,j)])
    print(ans)

Solution (Python):
N,M,S = map(int,input().split())
edges = [[] for _ in range(2500*50 + 100)]
def indexer(city,coin):
    return 50*coin + city

for _ in range(M):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    for scoin in range(a,2501):
        edges[indexer(u,scoin)].append((b,indexer(v,scoin-a)))
        edges[indexer(v,scoin)].append((b,indexer(u,scoin-a)))

for i in range(N):
    c,d = map(int,input().split())
    for scoin in range(c,2501):
        edges[indexer(i,scoin-c)].append((d,indexer(i,scoin)))


def dijkstra(s,n,edges):
    import heapq
    dist = [float('inf')] * n
    fixed = [False]*n
    dist[s] = 0
    fixed[s] = True
    priority_que = []
    for e in edges[s]:
        heapq.heappush(priority_que,e)

    while len(priority_que):
        edge = heapq.heappop(priority_que)
        if fixed[edge[1]]:
            continue
        v = edge[1]
        dist[v] = edge[0]
        fixed[v] = True
        for ne in edges[v]:
            heapq.heappush(priority_que,(ne[0]+dist[v], ne[1]))
    return dist

d=dijkstra(indexer(0,min(2500,S)),2500*50 + 100,edges)
for i in range(1,N):
    ans = float('inf')
    for j in range(2501):
        ans = min(ans,d[indexer(i,j)])
    print(ans)

Solution (Python):
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True








class SegTree:

    def __init__(self,n,init_ls=None,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        
        if init_ls==None:
            for i in range(n):
                self.seg[i+self.num-1]=init_val
        else:
            for i in range(n):
                self.seg[i+self.num-1]=init_ls[i]
        
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p >>= 1
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)

def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

ans=0

n,m,s=LI()
t_ls=[]
k=1+n*50
s=min(k-1,s)
for i in range(m):
    u,v,a,b=LI()
    u-=1
    v-=1
    for j in range(a,k):
        t_ls+=[(u*k+j,v*k+j-a,b)]
        t_ls+=[(v*k+j,u*k+j-a,b)]

for i in range(n):
    c,d=LI()
    for j in range(k):
        t_ls+=[(i*k+j,i*k+min(j+c,k-1),d)]

gt,_=GI(n*k,len(t_ls),ls=t_ls,Directed=True,index=0)
dist_t,_=dijkstra(gt,0*k+s)

for i in range(1,n):
    ans=inf
    for j in range(k):
        alt=dist_t[i*k+j]
        if alt<ans:
            ans=alt
    print(ans)

Solution (Python):

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, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a

limit = Amax*(N-1)
S = min(S, limit)
graph = [[] for _ in range(N+1)] 
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start):
    
    INF = 10 ** 15
    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev-1]
        si = min(limit, silver+c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time+d, si, prev))
            si += c; si = min(limit, si)
            time += d
            
    return dist

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

Solution (Python):
import queue
def dijkstra(n,EdgeMatrix,start):

    NodeList=queue.PriorityQueue() 
    Distance=[float('inf')]*n 
    used=[False]*n 

    Distance[start]=0 
    used[start]=True 
    LastNode=start 
    NodeList.put([0,start])
    Flag=True 
    
    while Flag:
        Flag=False
        for i in range(len(EdgeMatrix[LastNode])):
            
            Edge=EdgeMatrix[LastNode][i]
            if used[Edge[0]]==False and Distance[Edge[0]]>Distance[LastNode]+Edge[1]:
                    Distance[Edge[0]]=Distance[LastNode]+Edge[1]
                    NodeList.put([Distance[Edge[0]],Edge[0]])

        
        while not NodeList.empty():
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                Flag=True
                break

        LastNode=minNode[1] 
        used[minNode[1]]=True 
    return Distance


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


EdgeMatrix=[[] for i in range(125000)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2500):
        EdgeMatrix[(u-1)*2500+j].append([(v-1)*2500+j-a,b])
        EdgeMatrix[(v-1)*2500+j].append([(u-1)*2500+j-a,b])

for i in range(n):
    c,d=map(int,input().split())
    for j in range(2450):
        EdgeMatrix[i*2500+j].append([min(i*2500+j+c,(i+1)*2500-1),d])



    

Distance=dijkstra(125000,EdgeMatrix,min(s,2499))

for i in range(1,n):
    print(min(Distance[i*2500:(i+1)*2500-1]))

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