Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d = [min(d[0],d1[i]+d2[i])] + d
[print(10**15-c) for c in d]

Fixed submission:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = [float('inf')]*(n+1)
    d[s] = 0
    hq = [(0,s)]
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                heapq.heappush(hq,(c,v))
    return d

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

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1 = gijkstra(n,E,key=1,s=s)
d2 = gijkstra(n,E,key=2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d = [min(d[0],d1[i]+d2[i])] + d
[print(10**15-c) for c in d]

Fixed submission:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                p[v] = u
                heapq.heappush(hq,(c,v))
    return d, p

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

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1, _ = gijkstra(n,E,key=1,s=s)
d2, _ = gijkstra(n,E,key=2,s=t)
d = [10**15 - d1[-1] -d2[-1]]
for i in range(n-1,0,-1):
    d = [max(d[0], 10**15 - d1[i] -d2[i])] + d
[print(c) for c in d]

Fixed submission:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                p[v] = u
                heapq.heappush(hq,(c,v))
    return d, p

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

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1, _ = gijkstra(n,E,key=1,s=s)
d2, _ = gijkstra(n,E,key=2,s=t)
d = [d1[v]+d2[v] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(d[i+1:]))

Fixed submission:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = {i:float('inf') for i in range(1,n+1)}
    p = {i:-1 for i in range(1,n+1)}
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                p[v] = u
                heapq.heappush(hq,(c,v))
    return d, p

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

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1, _ = gijkstra(n,E,key=1,s=s)
d2, _ = gijkstra(n,E,key=2,s=t)
d = [d1[v]+d2[v] for v in range(1,n+1)]
for i in range(n):
    print(10**15 - min(d[i:]))

Fixed submission:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def gijkstra(n,E,key=1,s=1):
    T, HQ = [[float('inf'), -1] for i in range(n+1)], [(0,s)]
    T[s][0] = 0
    while HQ:
        u = heapq.heappop(HQ)[1]
        for e in E[u]:
            d, v = T[u][0] + e[key], e[0]
            if T[v][0] > d:
                T[v] = [d, u]
                heapq.heappush(HQ,(d,v))
    return T

n, m, s, t =  map(int,input().split())
E = [[] for i in range(n+1)]
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append(e[1:2]+e[2:])
    E[e[1]].append(e[0:1]+e[2:])
T1 = gijkstra(n,E,key=1,s=s)
T2 = gijkstra(n,E,key=2,s=t)
T = [T1[v][0]+T2[v][0] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(T[i+1:]))

Fixed submission:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]

Buggy python submission (verdict: Time Limit Exceeded):
def gijkstra(n,E,key=1,s=1):
    T, Q = [[float('inf'), -1] for i in range(n+1)], list(range(1,n+1))
    T[s][0] = 0
    Q.sort(key=lambda x:-T[x][0])
    while Q:
        u = Q.pop()
        for e in E[u]:
            v = e[0]
            d = T[u][0] + e[key]
            if T[v][0] > d:
                T[v] = [d, u]
                Q.sort(key=lambda x:-T[x][0])
    return T

n, m, s, t =  map(int,input().split())
E = [[] for i in range(n+1)]
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append(e[1:2]+e[2:])
    E[e[1]].append(e[0:1]+e[2:])
T1 = gijkstra(n,E,key=1,s=s)
T2 = gijkstra(n,E,key=2,s=t)
T = [T1[v][0]+T2[v][0] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(T[i+1:]))

Fixed submission:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]

Buggy python submission (verdict: Time Limit Exceeded):
def gijkstra(n,E,key=1,s=1):
    T, Q = [[float('inf'), -1] for i in range(n+1)], list(range(1,n+1))
    T[s][0] = 0
    while Q:
        u = min(Q, key=lambda x:T[x][0])
        Q.remove(u)
        for e in E[u]:
            v = e[0]
            d = T[u][0] + e[key]
            if T[v][0] > d:
                T[v] = [d, u]
    return T

n, m, s, t =  map(int,input().split())
E = [[] for i in range(n+1)]
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append(e[1:2]+e[2:])
    E[e[1]].append(e[0:1]+e[2:])
T1 = gijkstra(n,E,key=1,s=s)
T2 = gijkstra(n,E,key=2,s=t)
T = [T1[v][0]+T2[v][0] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(T[i+1:]))

Fixed submission:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]