Buggy python submission (verdict: Time Limit Exceeded):
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)
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)]
ans[1][S] = 0
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] < t:
        continue
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            ans[nv][nw] = t + nt
            heappush(dq,(t+nt,nw,nv))

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





Fixed submission:
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)]
#CD = [[0,0]] + [[10**9,10**9] 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]))

Buggy python submission (verdict: Time Limit Exceeded):
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)
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
    ans[v][w] = t
    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]))





Fixed submission:
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)]
#CD = [[0,0]] + [[10**9,10**9] 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]))

Buggy python submission (verdict: Time Limit Exceeded):
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)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[u+N*i].append((v+N*(i-a),b))
        g[v+N*i].append((u+N*(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+N*c].append((i+N*(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
    ans[v][w] = t
    for temp, nt in g[v+N*w]:
        nv = ((temp-1) % N)+1
        nw = (temp-1) // N
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

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





Fixed submission:
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)]
#CD = [[0,0]] + [[10**9,10**9] 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]))

Buggy python submission (verdict: Time Limit Exceeded):
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)
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
    ans[v][w] = t
    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]))





Fixed submission:
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)]
#CD = [[0,0]] + [[10**9,10**9] 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]))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.buffer.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)
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)

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,1,S)]

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

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





Fixed submission:
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)]
#CD = [[0,0]] + [[10**9,10**9] 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]))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.buffer.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)
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)

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,1,S)]
heapify(dq)

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

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





Fixed submission:
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)]
#CD = [[0,0]] + [[10**9,10**9] 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]))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.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)
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)

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 = [((1,S),0)]

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

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






Fixed submission:
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)]
#CD = [[0,0]] + [[10**9,10**9] 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]))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
A = {}
B = {}
g = defaultdict(list)
for u,v,a,b in UVAB:
    A[(u+v,u*v)] = a
    B[(u+v,u*v)] = b
mc = max(A.values())* M
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)

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 = [((1,S),0)]

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

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






Fixed submission:
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)]
#CD = [[0,0]] + [[10**9,10**9] 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]))