Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = []
    S = 1
    for _ in range(m):
        u, v, a, b = map(int,input().split())
        u -= 1; v -= 1
        E.append((u, v, -a, b)) # a : cost of silver
        S += a
    for v in range(n):
        c, d = map(int,input().split()) # c : earning silver
        E.append((v, v, c, d))

    dp = [[INF] * S for _ in range(n)]
    dp[0][min(s, S - 1)] = 0

    # 基本的には Bellman - Ford で確定
    for _ in range(2 * n - 2):
        for u, v, ds, dt in E:
            for s in range(S):
                ns = s + ds
                if not (0 <= ns < S):
                    continue
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)

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

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = [None] * m
    S = 0
    for i in range(m):
        u, v, a, b = map(int,input().split())
        S += a
        E[i] = (u - 1, v - 1, -a, b)

    exchange = [tuple(map(int,input().split())) for _ in range(n)]
    dp = [[INF] * (S + 1) for _ in range(n)]
    dp[0][min(s, S)] = 0

    for _ in range(2 * n - 3):
        # 先に両替を済ませる
        for v in range(n):
            for s in range(S + 1):
                ds, dt = exchange[v]
                dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt)
        # 移動する
        for u, v, ds, dt in E:
            for s in range(S + 1):
                ns = s + ds
                if ns < 0:
                    continue
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)

    for v in range(1, n):
        print(min(dp[v][j] for j in range(S + 1)))
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = []
    for _ in range(m):
        u, v, a, b = map(int,input().split())
        u -= 1; v -= 1
        E.append((u, v, -a, b)) # a : cost of silver
    for v in range(n):
        c, d = map(int,input().split()) # c : earning silver
        E.append((v, v, c, d))

    S = 5050 # silver を 5000 以上稼ぐ必要はない
    dp = [[INF] * S for _ in range(n)]
    dp[0][min(s, S - 1)] = 0

    # 基本的には Bellman - Ford で確定
    for _ in range(2 * n + 2):
        for u, v, ds, dt in E:
            for s in range(S):
                ns = s + ds
                if not (0 <= ns < S):
                    continue
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)

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

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = [None] * m
    S = 0
    for i in range(m):
        u, v, a, b = map(int,input().split())
        S += a
        E[i] = (u - 1, v - 1, -a, b)

    exchange = [tuple(map(int,input().split())) for _ in range(n)]
    dp = [[INF] * (S + 1) for _ in range(n)]
    dp[0][min(s, S)] = 0

    for _ in range(2 * n - 3):
        # 先に両替を済ませる
        for v in range(n):
            for s in range(S + 1):
                ds, dt = exchange[v]
                dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt)
        # 移動する
        for u, v, ds, dt in E:
            for s in range(S + 1):
                ns = s + ds
                if ns < 0:
                    continue
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)

    for v in range(1, n):
        print(min(dp[v][j] for j in range(S + 1)))
resolve()