Buggy python submission (verdict: Time Limit Exceeded):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, min(S, A), 0]]
    while len(s) > 0:
        s = sorted(s, key=lambda x: x[2])[::-1]
        u, i, x  = s.pop()
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            s.append([u, ni, dp[u, ni]])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                s.append([v, i-a, dp[v, i-a]])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                s.append([v, i, dp[v, i]])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Fixed submission:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from heapq import heappop, heappush
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, 0, min(S, A)]]
    while len(s) > 0:
        x, u, i  = heappop(s)
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            heappush(s, [dp[u, ni], u, ni])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                heappush(s, [dp[v, i-a], v, i-a])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                heappush(s, [dp[v, i], v, i])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict, deque
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = deque([[0, min(S, A)]])
    while len(s) > 0:
        tu, i = s.popleft()
        for vab in uvab[tu]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[tu, i] + b:
                dp[v, i-a] = dp[tu, i] + b
                s.append([v, i-a])
            elif i == A and dp[v, i] > dp[tu, i] + b:
                dp[v, i] = dp[tu, i] + b
                s.append([v, i])
        c, d = cd[tu]
        t = i
        while t < A:
            nt = min(t+c, A)
            if dp[tu, nt] > dp[tu, t] + d:
                dp[tu, nt] = dp[tu, t] + d
                s.append([tu, nt])
            t = nt
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Fixed submission:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from heapq import heappop, heappush
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, 0, min(S, A)]]
    while len(s) > 0:
        x, u, i  = heappop(s)
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            heappush(s, [dp[u, ni], u, ni])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                heappush(s, [dp[v, i-a], v, i-a])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                heappush(s, [dp[v, i], v, i])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict, deque
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = deque([[0, min(S, A)]])
    while len(s) > 0:
        tu, i = s.popleft()
        for vab in uvab[tu]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] >= dp[tu, i] + b:
                dp[v, i-a] = dp[tu, i] + b
                s.append([v, i-a])
            elif i == A and dp[v, i] >= dp[tu, i] + b:
                dp[v, i] = dp[tu, i] + b
                s.append([v, i])
        c, d = cd[tu]
        t = i
        while t < A:
            nt = min(t+c, A)
            if dp[tu, nt] > dp[tu, t] + d:
                dp[tu, nt] = dp[tu, t] + d
                s.append([tu, nt])
            t = nt
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Fixed submission:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from heapq import heappop, heappush
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, 0, min(S, A)]]
    while len(s) > 0:
        x, u, i  = heappop(s)
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            heappush(s, [dp[u, ni], u, ni])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                heappush(s, [dp[v, i-a], v, i-a])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                heappush(s, [dp[v, i], v, i])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()