Buggy python submission (verdict: Time Limit Exceeded):
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

max_silver = 50 * m    # これだけ持ってたらどの都市へも行ける

# n <= 50, m <= 100, max_silver <= 5000

# (都市,必要銀貨)を頂点とする最短経路問題

# 目的都市
for dest in range(2, n+1):
    # Dijkstra
    dist = {(dest, 0): 0}  # 開始頂点のみ距離0
    queue = [(0, dest, 0)]

    while len(queue) > 0:
        di, u, si = heapq.heappop(queue)
        # 用済みのデータ
        if (u, si) in dist and di > dist[(u, si)]:
            continue
        # 都市1に到達
        if u == 1 and si <= s:
            print(di)
            break

        # uに直接行ける各都市
        for v, a, b in adj[u]:
            if si + a > max_silver:
                break
            xsi = si + a
            if (v, xsi) not in dist or \
                dist[(v, xsi)] > di + b:
                dist[(v, xsi)] = di + b
                heapq.heappush(queue, (di + b, v, xsi))
        # 両替による遷移
        c, d = exch[u]
        xsi = max(si - c, 0)
        if (u, xsi) not in dist or \
            dist[(u, xsi)] > di + d:
            dist[(u, xsi)] = di + d
            heapq.heappush(queue, (di + d, u, xsi))


Fixed submission:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])

Buggy python submission (verdict: Time Limit Exceeded):
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

max_silver = 50 * m    # これだけ持ってたらどの都市へも行ける
s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])


Fixed submission:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])

Buggy python submission (verdict: Time Limit Exceeded):
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

max_silver = 50 * m    # これだけ持ってたらどの都市へも行ける
s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]

dmin = {u: float('inf') for u in range(1, n+1)} # dmin[u] = min(dist[(u, si)]
dmin[1] = 0

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 無効なデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    dmin[u] = min(dmin[u], di)
    for v, a, b in adj[u]:
        if si < a:
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])


Fixed submission:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])

Buggy python submission (verdict: Time Limit Exceeded):
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

max_silver = 50 * m    # これだけ持ってたらどの都市へも行ける
s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 無効なデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    for v, a, b in adj[u]:
        if si < a:
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    x = min(dist[(u, si)] for si in range(0, max_silver+1) if (u, si) in dist)
    print(x)


Fixed submission:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])

Buggy python submission (verdict: Time Limit Exceeded):
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

max_silver = 50 * m    # これだけ持ってたらどの都市へも行ける
s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 無効なデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    for v, a, b in adj[u]:
        if si < a:
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    x = min(dist[(u, si)] for si in range(0, max_silver+1) if (u, si) in dist)
    print(x)


Fixed submission:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])

Buggy python submission (verdict: Time Limit Exceeded):
# E - Two Currencies

n, m, s = map(int, input().split())
edge = []
for i in range(m):
    u, v, a, b = map(int, input().split())
    edge.append((u, v, a, b)) # from, to, 料金, 時間
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

# 料金の総和
max_silver = sum(a for u, v, a, b in edge)
s = min(s, max_silver) # max_silverまでで十分

# (都市,銀貨)を頂点とする最短経路問題
# Bellman-Ford
dist = {(1, s): 0}
for i in range(n * max_silver):
    for e in edge:
        u, v, a, b = e
        for sil in range(a, max_silver+1):
            xsil = sil - a
            if (u, sil) in dist:
                if (v, xsil) not in dist or \
                    dist[(v, xsil)] > dist[(u, sil)] + b:
                    dist[(v, xsil)] = dist[(u, sil)] + b
            if (v, sil) in dist:
                if (u, xsil) not in dist or \
                    dist[(u, xsil)] > dist[(v, sil)] + b:
                    dist[(u, xsil)] = dist[(v, sil)] + b
    for u in range(1, n+1):
        for sil in range(0, max_silver+1):
            c, d = exch[u]
            xsil = min(sil + c, max_silver)
            if (u, sil) in dist:
                if (u, xsil) not in dist or \
                    dist[(u, xsil)] > dist[(u, sil)] + d:
                    dist[(u, xsil)] = dist[(u, sil)] + d

for u in range(2, n+1):
    x = min(dist[(u, sil)] for sil in range(0, max_silver+1)
            if (u, sil) in dist)
    print(x)


Fixed submission:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])

Buggy python submission (verdict: Time Limit Exceeded):
# E - Two Currencies

n, m, s = map(int, input().split())
#adj = {u: [] for u in range(1, n+1)}
edge = []
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    #adj[u].append((v, a, b)) # 行き先, 料金, 時間
    #adj[v].append((u, a, b))
    edge.append((u, v, a, b)) # from, to, 料金, 時間
    max_silver += a # 料金の総和
exch = {}
max_rate = 0
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間
    max_rate = max(max_rate, c)
max_silver += max_rate - 1
s = min(s, max_silver)

# (都市,銀貨)を頂点とする最短経路問題

dist = {(1, s): 0}
for i in range(n * max_silver):
    for e in edge:
        u, v, a, b = e
        for sil in range(a, max_silver+1):
            if (u, sil) in dist:
                if (v, sil - a) not in dist or \
                    dist[(v, sil - a)] > dist[(u, sil)] + b:
                    dist[(v, sil - a)] = dist[(u, sil)] + b
            if (v, sil) in dist:
                if (u, sil - a) not in dist or \
                    dist[(u, sil - a)] > dist[(v, sil)] + b:
                    dist[(u, sil - a)] = dist[(v, sil)] + b
    for u in range(1, n+1):
        for sil in range(0, max_silver+1):
            c, d = exch[u]
            if (u, sil) in dist:
                if (u, sil + c) not in dist or \
                    dist[(u, sil + c)] > dist[(u, sil)] + d:
                    dist[(u, sil + c)] = dist[(u, sil)] + d

for u in range(2, n+1):
    x = min(dist[(u, sil)] for sil in range(0, max_silver+1)
            if (u, sil) in dist)
    print(x)


Fixed submission:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])