Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
input = sys.stdin.readline

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


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

    INF = float('inf')

    cost_yen = [[INF for i in range(n)] for j in range(n)]
    cost_snuuk = [[INF for i in range(n)] for j in range(n)]

    for train in trains:
        u, v, a, b = train
        cost_yen[u-1][v-1] = a
        cost_yen[v-1][u-1] = a
        cost_snuuk[u-1][v-1] = b
        cost_snuuk[v-1][u-1] = b

    d_yen = dijkstra(s-1, n, m, cost_yen)
    d_snuuk = dijkstra(t-1, n, m, cost_snuuk)


    cost_sum = [[d_yen[i]+d_snuuk[i], i+1] for i in range(n)]
    heapq.heapify(cost_sum)
    c, l = heapq.heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heapq.heappop(cost_sum)
        print(10**15 - c)

if __name__ == '__main__':
     main()
    






Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
import cProfile
input = sys.stdin.readline

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


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

    INF = float('inf')

    cost_yen = [[INF for i in range(n)] for j in range(n)]
    cost_snuuk = [[INF for i in range(n)] for j in range(n)]

    for train in trains:
        u, v, a, b = train
        cost_yen[u-1][v-1] = a
        cost_yen[v-1][u-1] = a
        cost_snuuk[u-1][v-1] = b
        cost_snuuk[v-1][u-1] = b

    d_yen = dijkstra(s-1, n, m, cost_yen)
    d_snuuk = dijkstra(t-1, n, m, cost_snuuk)


    cost_sum = [[d_yen[i]+d_snuuk[i], i+1] for i in range(n)]
    heapq.heapify(cost_sum)
    c, l = heapq.heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heapq.heappop(cost_sum)
        print(10**15 - c)
main()
    






Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

input = sys.stdin.readline

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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)


cost_sum = [[d_yen[i]+d_snuuk[i], i+1] for i in range(n)]
heapq.heapify(cost_sum)
c, l = heapq.heappop(cost_sum)
for i in range(n):
    while l<=i:
        c, l = heapq.heappop(cost_sum)
    print(10**15 - c)

    






Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

input = sys.stdin.readline

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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)


cost_sum = [[d_yen[i]+d_snuuk[i], i+1] for i in range(n)]
heapq.heapify(cost_sum)
c, l = heapq.heappop(cost_sum)
for i in range(n):
    while l<=i:
        c, l = heapq.heappop(cost_sum)
    print(10**15 - c)

    






Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

""" def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d """

input = sys.stdin.readline

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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

G_yen = csgraph_from_dense(cost_yen, null_value=INF)
G_snuuk = csgraph_from_dense(cost_snuuk, null_value=INF)

d_yen = dijkstra(G_yen, indices=s-1)
d_snuuk = dijkstra(G_snuuk, indices=t-1)


cost_sum = [x+y for x, y in zip(d_yen, d_snuuk)]
for i in range(n):
    print(int(10**15 - min(cost_sum[i:])))




Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

input = sys.stdin.readline

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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)

for i in range(n):
    cost_sum = [x+y for x, y in zip(d_yen, d_snuuk)]
    print(10**15 - min(cost_sum))
    del d_yen[0]
    del d_snuuk[0]



Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

input = sys.stdin.readline

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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)

for i in range(n):
    cost_sum = [x+y for x, y in zip(d_yen[i:], d_snuuk[i:])]
    print(10**15 - min(cost_sum))



Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

input = sys.stdin.readline

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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)

for i in range(n):
    cost_sum = [x+y for x, y in zip(d_yen[i:], d_snuuk[i:])]
    print(10**15 - min(cost_sum))



Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

Buggy python submission (verdict: Time Limit Exceeded):
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


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

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)

for i in range(n):
    cost_sum = [x+y for x, y in zip(d_yen[i:], d_snuuk[i:])]
    print(10**15 - min(cost_sum))



Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()