Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


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

# yen_edges = [[] for _ in range(n)]
# snuke_edges = [[] for _ in range(n)]
# for l in sys.stdin.readlines():
#     u, v, yen, snuke = map(int, l.strip().split())
#     yen_edges[u - 1].append((v - 1, yen))
#     yen_edges[v - 1].append((u - 1, yen))
#     snuke_edges[u - 1].append((v - 1, snuke))
#     snuke_edges[v - 1].append((u - 1, snuke))

# yen_costs = dijkstra(n, yen_edges, s - 1)
# snuke_costs = dijkstra(n, snuke_edges, t - 1)

yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
             for _ in range(n)]
snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
               for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
    yen_edges[u - 1][v - 1] = yen
    yen_edges[v - 1][u - 1] = yen
    snuke_edges[u - 1][v - 1] = snuke
    snuke_edges[v - 1][u - 1] = snuke

yen_costs = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
snuke_costs = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)

final_costs = list(
    accumulate([yen + snuke
                for yen, snuke in zip(yen_costs, snuke_costs)][::-1],
               min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_cost = dijkstra(n, yen_edges, s - 1)
snuke_cost = dijkstra(n, snuke_edges, t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


n, m, s, t = map(int, input().split())
trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
             for _ in range(n)]
snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
               for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_edges[i - 1][j - 1] = yen
    yen_edges[j - 1][i - 1] = yen
    snuke_edges[i - 1][j - 1] = snuke
    snuke_edges[j - 1][i - 1] = snuke

yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
from heapq import heapify, heappop, heappush
INF = 10**15


def pq_replace(pq, item):
    target_val, target_id = item
    for j, (v, i) in enumerate(pq):
        if i == target_id:
            pq[j] = ((target_val, target_id))
            heapify(pq)
            return


def dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(dist, node) for node, dist in zip(range(num), dists)]
    heapify(priority_queue)

    while priority_queue:
        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    pq_replace(priority_queue, (dist_from_edge, node))

    return dists


def fast_dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(0, start)]

    for _ in range(num):

        if not priority_queue:
            break

        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    heappush(priority_queue, (dist_from_edge, node))

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]
# for l in sys.stdin.readlines():
#     u, v, a, b = map(int, l.strip().split())
#     trains = []
# trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
INF = 10**15


def pq_replace(pq, item):
    target_val, target_id = item
    for j, (v, i) in enumerate(pq):
        if i == target_id:
            pq[j] = ((target_val, target_id))
            heapify(pq)
            return


def dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(dist, node) for node, dist in zip(range(num), dists)]
    heapify(priority_queue)

    while priority_queue:
        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    pq_replace(priority_queue, (dist_from_edge, node))

    return dists


def fast_dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(0, start)]

    for _ in range(num):

        if not priority_queue:
            break

        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    heappush(priority_queue, (dist_from_edge, node))

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
INF = 10**15


def pq_replace(pq, item):
    target_val, target_id = item
    for j, (v, i) in enumerate(pq):
        if i == target_id:
            pq.remove((v, i))
            heappush(pq, (target_val, target_id))
            break


def dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(dist, node) for node, dist in zip(range(num), dists)]
    heapify(priority_queue)

    while priority_queue:
        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    pq_replace(priority_queue, (dist_from_edge, node))

    return dists


def fast_dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(0, start)]

    for _ in range(num):

        if not priority_queue:
            break

        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    heappush(priority_queue, (dist_from_edge, node))

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = fast_dijkstra(yen_graph, start=s - 1)
snuke_cost = fast_dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
INF = 10**15

# def dijkstra(graph, start=0, inf=INF):

#     num = len(graph)
#     remains = [node for node in range(num)]
#     dists = [inf if node != start else 0 for node in range(num)]

#     while remains:
#         min_index = min(remains, key=lambda x: dists[x])
#         remains.remove(min_index)

#         target_edges = graph[min_index]
#         for index, dist in enumerate(target_edges):
#             if dist != 0:
#                 dist_from_edge = dists[min_index] + dist
#                 if dists[index] > dist_from_edge:
#                     dists[index] = dist_from_edge

#     return dists


def dijkstra(graph, start=0, inf=INF):
    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    remains = dists[:]

    for _ in range(num):
        min_index = remains.index(min(remains))
        remains[min_index] = inf

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge
                    remains[index] = dist_from_edge

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
INF = 10**15


def dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [inf if node != start else 0 for node in range(num)]

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import math


def dijkstra(graph, start=0):

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import math


def dijkstra(graph, start=0, goal=None, verbose=0):
    '''
    sample input:
    graph = [[0, 2, 5, 4, 0, 0], # node 0
             [2, 0, 0, 3, 6, 0], # node 1
             [5, 0, 0, 2, 0, 6], # node 2
             [4, 3, 2, 0, 2, 0], # node 3
             [0, 6, 0, 2, 0, 4], # node 4
             [0, 0, 6, 0, 4, 0]  # node 5
    ]
    (
    1. distance from a node itself should be 0,
    2. if there is no edge between nodes, the distance between them should be 0
    3. weights can be negative
    )
    '''

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]
    prevs = [-1 for node in range(num)]
    if goal is None:
        goal = num - 1

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge
                    prevs[index] = min_index

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import math


def dijkstra(graph, start=0, goal=None, verbose=0):
    '''
    sample input:
    graph = [[0, 2, 5, 4, 0, 0], # node 0
             [2, 0, 0, 3, 6, 0], # node 1
             [5, 0, 0, 2, 0, 6], # node 2
             [4, 3, 2, 0, 2, 0], # node 3
             [0, 6, 0, 2, 0, 4], # node 4
             [0, 0, 6, 0, 4, 0]  # node 5
    ]
    (
    1. distance from a node itself should be 0,
    2. if there is no edge between nodes, the distance between them should be 0
    3. weights can be negative
    )
    '''

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]
    prevs = [-1 for node in range(num)]
    if goal is None:
        goal = num - 1

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge
                    prevs[index] = min_index

    min_route = []
    prev = goal
    cnt = 0
    while prev != start:
        min_route.append(prev)
        prev = prevs[prev]

        cnt += 1
        if prev == -1 or cnt > num:
            raise NoRouteError(
                'There is no possible route in this graph \ngraph: {} \nstart: {} \ngoal: {}'.
                format(graph, start, goal))

    else:
        min_route.append(prev)
    min_route = min_route[::-1]
    min_dist = dists[goal]

    if verbose:
        print('---route---')
        for node in min_route[:-1]:
            print('{} -> '.format(node), end='')
        else:
            print(min_route[-1])

        print('---distance---')
        print(min_dist)

    return dists, min_route


class NoRouteError(Exception):
    pass


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_dist, min_route = dijkstra(yen_graph, start=s - 1)
snuke_dist, min_route = dijkstra(snuke_graph, start=t - 1)

for i in range(n):
    asset = 10**15
    asset -= min(
        [yen + snuke for yen, snuke in zip(yen_dist[i:], snuke_dist[i:])])
    print(asset)


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)