CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    import heapq
    
    def dijkstra(graph,start,cd,s):
        dist = [[float("inf")]*2505 for _ in range(n)]
        q = []
        dist[start][s] = 0
        heapq.heappush(q, (0,start,s))
        
        while q:
            cost, cur_node,coin = heapq.heappop(q)
            
            if dist[cur_node][coin] < cost:
                continue
            
            for nex_node,nex_cost,nex_time  in graph[cur_node]:
                if coin >= nex_cost and dist[nex_node][coin-nex_cost] > cost+nex_time:
                    dist[nex_node][coin-nex_cost] = cost+nex_time
                    heapq.heappush(q, (cost+nex_time,nex_node,coin-nex_cost))
            if dist[cur_node][min(2500,coin+cd[cur_node][0])] > cost+cd[cur_node][1]:
                 dist[cur_node][min(2500,coin+cd[cur_node][0])] = cost+cd[cur_node][1]
                 heapq.heappush(q,(cost+cd[cur_node][1],cur_node,min(2500,coin+cd[cur_node][0])))
                    
        for i in dist[1:]:
            print((min(i)))
    n,m,s = list(map(int,input().split()))
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u,v,a,b = list(map(int,input().split()))
        u -= 1
        v-= 1
        la.append(a)
        E[u].append((v,a,b))
        E[v].append((u,a,b))

    cd = [list(map(int,input().split())) for i in range(n)]

    dijkstra(E,0,cd,min(s,2500))
if __name__ == "__main__":
    main()

# Optimized solution
def main():
    import heapq
    
    def dijkstra(graph,s,cd,c):
        dist = [[float("inf")]*2505 for _ in range(n)]
        q = []
        dist[s][c] = 0
        heapq.heappush(q, (0,s,c))
        
        while q:
            d, p,c = heapq.heappop(q)
            
            if dist[p][c] < d:
                continue
            
            for nn,nc,nt  in graph[p]:
                if c >= nc and dist[nn][c-nc] >   d+nt:
                    dist[nn][c-nc] =    d+nt
                    heapq.heappush(q,(d+nt,nn,c-nc))
            if c+cd[p][0] < 2500:
                if dist[p][c+cd[p][0]] >  d+cd[p][1]:
                    dist[p][c+cd[p][0]] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,c+cd[p][0]))
            else:
                if dist[p][2500] >  d+cd[p][1]:
                    dist[p][2500] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,2500))
                    
        for i in dist[1:]:
            print((min(i)))
    n,m,s = list(map(int,input().split()))
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u,v,a,b = list(map(int,input().split()))
        u -= 1
        v-= 1
        la.append(a)
        E[u].append((v,a,b))
        E[v].append((u,a,b))

    cd = [list(map(int,input().split())) for i in range(n)]

    dijkstra(E,0,cd,min(s,2500))
if __name__ == "__main__":
    main()
# Original solution
import heapq


n, m, s = list(map(int, input().split()))
if s >= 2500:
    s = 2499

edges = [[] for _ in range(n)]
for _ in range(m):
    from_, to, cost, time = list(map(int, input().split()))
    edges[from_-1].append((to-1, cost, time))
    edges[to-1].append((from_-1, cost, time))

banks = [(0, 0) for _ in range(n)]
for i in range(n):
    coin, time = list(map(int, input().split()))
    banks[i] = (coin, time)

INF = float('INF')
DP = [INF] * (n * 2500)
ans = [INF] * n


def to_one_dimension(node, coin):
    return node * 2500 + coin


def push_todo(node, coin, time):
    if coin < 0:
        return
    if time >= DP[to_one_dimension(node, coin)]:
        return
    heapq.heappush(todo, (time, node, coin))


def charge(node, current_coin, current_time):
    coin, time = banks[node]
    new_coin = current_coin + coin
    if new_coin >= 2500:
        new_coin = 2499
    push_todo(node, new_coin, current_time+time)


todo = [(0, 0, s)]
while todo:
    current_time, node, current_coin = heapq.heappop(todo)
    if current_time < ans[node]:
        ans[node] = current_time

    one_d_idx = to_one_dimension(node, current_coin)
    if current_time >= DP[one_d_idx]:
        continue

    DP[one_d_idx] = current_time
    charge(node, current_coin, current_time)

    for to, cost, time in edges[node]:
        push_todo(to, current_coin-cost, current_time+time)

for a in ans[1:]:
    print(a)


# Optimized solution
import heapq


n, m, s = list(map(int, input().split()))
if s >= 2500:
    s = 2499

edges = [[] for _ in range(n)]
for _ in range(m):
    from_, to, cost, time = list(map(int, input().split()))
    edges[from_-1].append((to-1, cost, time))
    edges[to-1].append((from_-1, cost, time))

banks = []
for i in range(n):
    coin, time = list(map(int, input().split()))
    banks.append((coin, time))

INF = float('INF')
DP = [[INF] * 2500 for _ in range(n)]
ans = [INF] * n


def push_todo(node, coin, time):
    if coin < 0:
        return
    if time >= DP[node][coin]:
        return
    heapq.heappush(todo, (time, node, coin))


def charge(node, current_coin, current_time):
    coin, time = banks[node]
    new_coin = current_coin + coin
    if new_coin >= 2500:
        new_coin = 2499
    push_todo(node, new_coin, current_time+time)


todo = [(0, 0, s)]
while todo:
    current_time, node, current_coin = heapq.heappop(todo)
    if current_time >= DP[node][current_coin]:
        continue

    if current_time < ans[node]:
        ans[node] = current_time

    DP[node][current_coin] = current_time
    charge(node, current_coin, current_time)

    for to, cost, time in edges[node]:
        push_todo(to, current_coin-cost, current_time+time)

for a in ans[1:]:
    print(a)
# Original solution
def main():    
    import heapq
    
    n, m, s = list(map(int, input().split()))
    if s >= 2500:
        s = 2499
    
    edges = [[] for _ in range(n)]
    for _ in range(m):
        from_, to, cost, time = list(map(int, input().split()))
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))
    
    banks = []
    for i in range(n):
        coin, time = list(map(int, input().split()))
        banks.append((coin, time))
    
    INF = float('INF')
    DP = [[INF] * 2500 for _ in range(n)]
    ans = [INF] * n
    
    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
    
    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin >= 2500:
            new_coin = 2499
        push_todo(node, new_coin, current_time+time)
    
    todo = [(0, 0, s)]
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time >= DP[node][current_coin]:
            continue
    
        if current_time < ans[node]:
            ans[node] = current_time
    
        DP[node][current_coin] = current_time
        charge(node, current_coin, current_time)
    
        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)
    
    for a in ans[1:]:
        print(a)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    import heapq

    n, m, s = list(map(int, input().split()))
    if s >= 2500:
        s = 2499

    edges = [[] for _ in range(n)]
    for _ in range(m):
        from_, to, cost, time = list(map(int, input().split()))
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))

    banks = []
    for i in range(n):
        coin, time = list(map(int, input().split()))
        banks.append((coin, time))

    INF = float('INF')
    DP = [[INF] * 2500 for _ in range(n)]
    DP[0][s] = 0
    ans = [INF] * n

    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time

    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin >= 2500:
            new_coin = 2499
        push_todo(node, new_coin, current_time+time)

    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time > DP[node][current_coin]:
            continue

        if current_time < ans[node]:
            ans[node] = current_time

        charge(node, current_coin, current_time)

        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)

    for a in ans[1:]:
        print(a)


if __name__ == '__main__':
    main()
# Original solution
def main():
    import heapq

    n, m, s = list(map(int, input().split()))
    if s >= 2500:
        s = 2499

    edges = [[] for _ in range(n)]
    for _ in range(m):
        from_, to, cost, time = list(map(int, input().split()))
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))

    banks = []
    for i in range(n):
        coin, time = list(map(int, input().split()))
        banks.append((coin, time))

    INF = float('INF')
    DP = [[INF] * 2500 for _ in range(n)]
    DP[0][s] = 0
    ans = [INF] * n

    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time

    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin >= 2500:
            new_coin = 2499
        push_todo(node, new_coin, current_time+time)

    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time > DP[node][current_coin]:
            continue

        if current_time < ans[node]:
            ans[node] = current_time

        charge(node, current_coin, current_time)

        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)

    for a in ans[1:]:
        print(a)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    import heapq

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

    edges = [[] for _ in range(n)]
    max_cost = 0
    for _ in range(m):
        from_, to, cost, time = list(map(int, input().split()))
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))
        if cost > max_cost:
            max_cost = cost

    banks = []
    for i in range(n):
        coin, time = list(map(int, input().split()))
        banks.append((coin, time))

    max_coin = max_cost * (n-1)
    if s > max_coin:
        s = max_coin

    INF = float('INF')
    DP = [[INF] * (max_coin+1) for _ in range(n)]
    DP[0][s] = 0

    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time

    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin > max_coin:
            new_coin = max_coin
        push_todo(node, new_coin, current_time+time)

    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time > DP[node][current_coin]:
            continue

        charge(node, current_coin, current_time)

        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)

    for node in range(1, n):
        print((min(DP[node])))


if __name__ == '__main__':
    main()
# Original solution
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    for _ in range(3):
        if d + dd < dp[v, s + c]:
            dp[v, s + c] = d + dd
            heapq.heappush(heap, (d + dd, v, s + c))

print(*ans[2:], sep='\n')


# Optimized solution
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    sc = min(s + c, 50 * N + 10)
    if d + dd < dp[v, sc]:
        dp[v, sc] = d + dd
        heapq.heappush(heap, (d + dd, v, sc))

print(*ans[2:], sep='\n')
# Original solution
from heapq import heappush, heappop

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, cost, dist = list(map(int, input().split()))
    mxCost = max(mxCost, cost)
    fr -= 1
    to -= 1
    edges[fr].append((to, dist, cost))
    edges[to].append((fr, dist, cost))

for i in range(N):
    C, D = list(map(int, input().split()))
    edges[i].append((i, D, -C))

que = [(0, S, 0)]
mxCost *= (N - 1)
minDsit = [[10**18] * (mxCost + 1) for _ in range(N)]
minDsit[0][0] = 0

while que:
    dist, s, now = heappop(que)

    for to, d, c in edges[now]:
        cost = min(mxCost, s - c)
        if cost < 0 or minDsit[to][cost] <= dist + d:
            continue
        minDsit[to][cost] = dist + d
        que.append((dist + d, cost, to))

for dist in minDsit[1:]:
    print((min(dist)))


# Optimized solution
from heapq import heappush, heappop

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, cost, dist = list(map(int, input().split()))
    mxCost = max(mxCost, cost)
    fr -= 1
    to -= 1
    edges[fr].append((to, dist, cost))
    edges[to].append((fr, dist, cost))

for i in range(N):
    C, D = list(map(int, input().split()))
    edges[i].append((i, D, -C))

que = [(0, S, 0)]
mxCost *= (N - 1)
minDsit = [[10**18] * (mxCost + 1) for _ in range(N)]
minDsit[0][0] = 0

while que:
    dist, s, now = heappop(que)

    for to, d, c in edges[now]:
        cost = min(mxCost, s - c)
        if cost < 0 or minDsit[to][cost] <= dist + d:
            continue
        minDsit[to][cost] = dist + d
        heappush(que, (dist + d, cost, to))

for dist in minDsit[1:]:
    print((min(dist)))
# Original solution
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()

# Optimized solution
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()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = list(map(int,input().split()))
    E = []
    S = 1
    for _ in range(m):
        u, v, a, b = list(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 = list(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()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = list(map(int,input().split()))
    E = [None] * m
    S = 0
    for i in range(m):
        u, v, a, b = list(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()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = list(map(int,input().split()))
    E = [None] * m
    S = 0
    for i in range(m):
        u, v, a, b = list(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()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    n, m, s = list(map(int,input().split()))
    S = 0
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = list(map(int,input().split())) # a : cost silver
        u -= 1; v -= 1
        S += a
        E[u].append((v, -a, b))
        E[v].append((u, -a, b))
    for v in range(n):
        c, d = list(map(int,input().split()))
        E[v].append((v, c, d))

    # Dijkstra with heap
    dist = [[INF] * (S + 1) for _ in range(n)]
    s = min(s, S)
    dist[0][s] = 0
    heap = [(0, 0, s)] # dist, vertex, silver
    while heap:
        d, v, s = heappop(heap)
        if dist[v][s] < d:
            continue
        for nv, ds, dd in E[v]:
            ns = s + ds
            if not (0 <= ns <= S):
                continue
            if dist[nv][ns] > dist[v][s] + dd:
                dist[nv][ns] = dist[v][s] + dd
                heappush(heap, (dist[nv][ns], nv, ns))

    # output
    for v in range(1, n):
        print((min(dist[v][s] for s in range(S + 1))))
resolve()