Buggy python submission (verdict: Time Limit Exceeded):
import sys

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, S, T = map(int, next(sys.stdin).split())
U = []
V = []
A = []
B = []
for _ in range(M):
    u, v, a, b = map(int, next(sys.stdin).split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)
graph_yen = coo_matrix((A, (U, V)), shape=(N + 1, N + 1))
graph_snuke = coo_matrix((B, (U, V)), shape=(N + 1, N + 1))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = dijkstra(graph_yen.tocsr(), indices=S, directed=False, unweighted=False)
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = dijkstra(graph_snuke.tocsr(), indices=T, directed=False, unweighted=False)

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))


Fixed submission:
import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

import numpy as np
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, S, T = list(map(int, input().split()))
graph_yen = lil_matrix((N + 1, N + 1))
graph_snuke = lil_matrix((N + 1, N + 1))
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u, v] = a
    graph_snuke[u, v] = b

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = dijkstra(graph_yen.tocsr(), indices=S, directed=False, unweighted=False)
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = dijkstra(graph_snuke.tocsr(), indices=T, directed=False, unweighted=False)

# total_mins[i]: i で両替して S から T まで行くときの最小金額
total_mins = 10 ** 15 - (yen_mins + snuke_mins)[1:]

# 後ろから累積最大値とる
for a in np.maximum.accumulate(total_mins[::-1])[::-1]:
    print(int(a))


Fixed submission:
import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, S, T = list(map(int, input().split()))
U = []
V = []
A = []
B = []
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

graph_yen = coo_matrix((A, (U, V)), shape=(N + 1, N + 1))
graph_snuke = coo_matrix((B, (U, V)), shape=(N + 1, N + 1))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = dijkstra(graph_yen.tocsr(), indices=S, directed=False, unweighted=False)
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = dijkstra(graph_snuke.tocsr(), indices=T, directed=False, unweighted=False)

# total_mins[i]: i で両替して S から T まで行くときの最小金額
total_mins = 10 ** 15 - (yen_mins + snuke_mins)[1:]

# 後ろから累積最大値とる
for a in np.maximum.accumulate(total_mins[::-1])[::-1]:
    print(int(a))


Fixed submission:
import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, S, T = list(map(int, input().split()))
U = []
V = []
A = []
B = []
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

graph_yen = coo_matrix((A, (U, V)), shape=(N + 1, N + 1))
graph_snuke = coo_matrix((B, (U, V)), shape=(N + 1, N + 1))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = dijkstra(graph_yen, indices=S, directed=False, unweighted=False)
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = dijkstra(graph_snuke, indices=T, directed=False, unweighted=False)

# total_mins[i]: i で両替して S から T まで行くときの最小金額
total_mins = 10 ** 15 - (yen_mins + snuke_mins)[1:]

# 後ろから累積最大値とる
for a in np.maximum.accumulate(total_mins[::-1])[::-1]:
    print(int(a))


Fixed submission:
import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))

Buggy python submission (verdict: Runtime Error):
import sys

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, S, T = list(map(int, input().split()))
U = []
V = []
A = []
B = []
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

graph_yen = coo_matrix((A, (U, V)), shape=(N + 1, N + 1))
graph_snuke = coo_matrix((B, (U, V)), shape=(N + 1, N + 1))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = dijkstra(graph_yen, indices=S, directed=False, unweighted=False)
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = dijkstra(graph_snuke, indices=T, directed=False, unweighted=False)

# total_mins[i]: i で両替して S から T まで行くときの最小金額
total_mins = 10 ** 15 - (yen_mins + snuke_mins)[1:]

# 後ろから累積最大値とる
for a in np.maximum.accumulate(total_mins[::-1])[::-1]:
    print(int(a))


Fixed submission:
import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))