Buggy python submission (verdict: Time Limit Exceeded):

import heapq

N, M, S, T = map(int, input().split())

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest, cost in adj[src].items():
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


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

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)



Fixed submission:
import heapq

N, M, S, T = map(int, input().split())

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest, cost in adj[src].items():
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


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

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)

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

N, M, S, T = map(int, input().split())

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


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

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)



Fixed submission:
import heapq

N, M, S, T = map(int, input().split())

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest, cost in adj[src].items():
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


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

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)

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


class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = len(adj)  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


N, M, S, T = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)



Fixed submission:
import heapq

N, M, S, T = map(int, input().split())

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest, cost in adj[src].items():
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


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

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)

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


class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = len(adj)  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


N, M, S, T = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)


Fixed submission:
import heapq

N, M, S, T = map(int, input().split())

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest, cost in adj[src].items():
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


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

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)

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


class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = len(adj)  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


N, M, S, T = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)


Fixed submission:
import heapq

N, M, S, T = map(int, input().split())

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest, cost in adj[src].items():
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


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

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)