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

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    for year in range(n):
        cost = min(total[year:])
        print(money - cost)

Fixed submission:
import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])

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

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    for year in range(n):
        for i in range(year, n):
            cost = min(total[year:])

        print(money - cost)

Fixed submission:
import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])

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

# dijkstra shortest path solver
def shortest_path(G, s, t):
    fixed = {}
    q = list()
    heapq.heappush(q, (0, s))

    while q:
        w,x = heapq.heappop(q)
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                heapq.heappush(q, (w + G[x][y] , y))
    return None

def memo(G, n, s):
    cost = list()
    for i in range(n):
        cost.append(shortest_path(G, s, i))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for i in range(n)] # JPY
    H = [{} for i in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = memo(G, n, S)
    min_snk = memo(H, n, T)
    for year in range(n):
        cost = None
        for i in range(year, n):
            t = min_jpy[i] + min_snk[i]
            if cost is None:
                cost = t
            else:
                if cost > t:
                    cost = t

        print(money - cost)


Fixed submission:
import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])

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

def setNode(n):
    global G
    global H
    G = [{} for i in range(n)]
    H = [{} for i in range(n)]

def addEdge(s, t, p, q):
    global G
    global H
    G[s][t]=p
    G[t][s]=p
    H[s][t]=q
    H[t][s]=q

# dijkstra shortest path solver
def shortest_path(G, s, t):
    fixed = {}
    q = list()
    heapq.heappush(q, (0, s))

    while q:
        w,x = heapq.heappop(q)
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                heapq.heappush(q, (w + G[x][y] , y))
    return None

if __name__ == '__main__':
    G = [{}] # JPY
    H = [{}] # SNK
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    setNode(n)

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        U = u-1
        V = v-1
        addEdge(U, V, p, q)

    for year in range(n):
        cost = None
        for exg in range(year, n):
            min_jpy = shortest_path(G, S, exg)
            min_snk = shortest_path(H, T, exg) # = shortest_path(exg, T)
            total = min_jpy + min_snk
            if cost is None:
                cost = total
            else:
                if cost > total:
                    cost = total
            #print("year:{}\t{}->{}->{}: JPY:{}, SNK:{}: total:{}".format(year, S,exg,T,min_jpy,min_snk, total))
        #print("year:{}\tminimum cost:{}, money:{}".format(year, cost, money-cost))
        print(money-cost)

Fixed submission:
import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])

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

def setNode(n):
    global G
    global H
    G = [{} for i in range(n)]
    H = [{} for i in range(n)]

def addEdge(s, t, p, q):
    global G
    global H
    G[s][t]=p
    G[t][s]=p
    H[s][t]=q
    H[t][s]=q

def shortest_path(G, s, t):
    fixed = {}
    q = queue.PriorityQueue()
    q.put((0,s))

    while q.empty() == False:
        w,x = q.get()
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                q.put((w + G[x][y], y))
    return None

if __name__ == '__main__':
    G = [{}] # JPY
    H = [{}] # SNK
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    setNode(n)

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        U = u-1
        V = v-1
        addEdge(U, V, p, q)

    for year in range(n):
        cost = None
        for exg in range(year, n):
            min_jpy = shortest_path(G, S, exg)
            min_snk = shortest_path(H, T, exg) # = shortest_path(exg, T)
            total = min_jpy + min_snk
            if cost is None:
                cost = total
            else:
                if cost > total:
                    cost = total
            #print("year:{}\t{}->{}->{}: JPY:{}, SNK:{}: total:{}".format(year, S,exg,T,min_jpy,min_snk, total))
        #print("year:{}\tminimum cost:{}, money:{}".format(year, cost, money-cost))
        print(money-cost)

Fixed submission:
import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])