Problem:
 Score : 400 points    Problem Statement Kenkoooo is planning a trip in Republic of Snuke.
In this country, there are n cities and m trains running.
The cities are numbered 1 through n , and the i -th train connects City u_i and v_i bidirectionally.
Any city can be reached from any city by changing trains.  Two currencies are used in the country: yen and snuuk.
Any train fare can be paid by both yen and snuuk.
The fare of the i -th train is a_i yen if paid in yen, and b_i snuuk if paid in snuuk.  In a city with a money exchange office, you can change 1 yen into 1 snuuk.
However, when you do a money exchange, you have to change all your yen into snuuk.
That is, if Kenkoooo does a money exchange when he has X yen, he will then have X snuuk.
Currently, there is a money exchange office in every city, but the office in City i will shut down in i years and can never be used in and after that year.  Kenkoooo is planning to depart City s with 10^{15} yen in his pocket and head for City t , and change his yen into snuuk in some city while traveling.
It is acceptable to do the exchange in City s or City t .  Kenkoooo would like to have as much snuuk as possible when he reaches City t by making the optimal choices for the route to travel and the city to do the exchange.
For each i=0,...,n-1 , find the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i years.
You can assume that the trip finishes within the year.      Constraints  2 \leq n \leq 10^5  1 \leq m \leq 10^5  1 \leq s,t \leq n  s \neq t  1 \leq u_i < v_i \leq n  1 \leq a_i,b_i \leq 10^9  If i\neq j , then u_i \neq u_j or v_i \neq v_j .  Any city can be reached from any city by changing trains.  All values in input are integers.         Input Input is given from Standard Input in the following format:  n  m  s  t  u_1  v_1  a_1  b_1  :  u_m  v_m  a_m  b_m       Output Print n lines.
In the i -th line, print the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i-1 years.        Sample Input 1 4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1      Sample Output 1 999999999999998
999999999999989
999999999999979
999999999999897  After 0 years, it is optimal to do the exchange in City 1 . After 1 years, it is optimal to do the exchange in City 2 . Note that City 1 can still be visited even after the exchange office is closed.
Also note that, if it was allowed to keep 1 yen when do the exchange in City 2 and change the remaining yen into snuuk, we could reach City 3 with 999999999999998 snuuk, but this is NOT allowed. After 2 years, it is optimal to do the exchange in City 3 . After 3 years, it is optimal to do the exchange in City 4 .
Note that the same train can be used multiple times.       Sample Input 2 8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879      Sample Output 2 999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    import heapq


    INF = 10 ** 15

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

    G_y = [[] for _ in range(N + 1)]
    G_s = [[] for _ in range(N + 1)]

    for _ in range(M):
        u, v, a, b = map(int, input().split())
        
        G_y[u].append([a, v])
        G_y[v].append([a, u])

        G_s[u].append([b, v])
        G_s[v].append([b, u])


    def dijksrea(s, G): 
        d = [INF] * (N + 1)
        d[s] = 0 
        pque = []
        heapq.heappush(pque, [0, s]) 

        while len(pque) != 0: 
            p = heapq.heappop(pque) 
            v = p[1] 
            if d[v] < p[0]: 
                continue
            for i in range(len(G[v])): 
                e = G[v][i]
                if d[e[1]] > d[v] + e[0]: 
                    d[e[1]] = d[v] + e[0]
                    heapq.heappush(pque, [d[e[1]], e[1]]) 
        
        return d

    d_y = dijksrea(S, G_y)
    d_s = dijksrea(T, G_s)

    
    

    ans = [0] * (N + 1)
    for i in range(N, 0, -1): 
        tmp = INF - d_y[i] - d_s[i]
        ans[i] = max(ans[i], tmp)
        ans[i - 1] = ans[i]

    print (*ans[1:], sep = '\n')

if __name__ == '__main__':
    main()

Solution (Python):
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
UVAB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for u,v,a,b in UVAB:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))

import heapq
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to,a,_ in es[v]:
        if c+a >= cy[to]: continue
        cy[to] = c+a
        heapq.heappush(hq, (c+a, to))
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to,_,b in es[v]:
        if c+b >= cs[to]: continue
        cs[to] = c+b
        heapq.heappush(hq, (c+b, to))

ans = [-1] * N
minc = INF
for i,(y,s) in reversed(list(enumerate(zip(cy,cs)))):
    minc = min(minc, y+s)
    ans[i] = 10**15 - minc
print(*ans, sep='\n')

Solution (Python):
import heapq


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    q = [(0, start)] 
    while q:
        d, v = heapq.heappop(q)
        if dist[v] < d:
            continue
        for nxt_v, cost in graph[v]:
            if dist[v] + cost < dist[nxt_v]:
                dist[nxt_v] = dist[v] + cost
                heapq.heappush(q, (dist[nxt_v], nxt_v))
    return dist


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

graph_y = [[] for i in range(n)]
graph_s = [[] for i in range(n)]
for u, v, a, b in info:
    u -= 1
    v -= 1
    graph_y[u].append((v, a))
    graph_y[v].append((u, a))
    graph_s[u].append((v, b))
    graph_s[v].append((u, b))
    
s -= 1
t -= 1
dist_y = dijkstra(s, graph_y)
dist_s = dijkstra(t, graph_s)

ans = 10 ** 18
ret = [10 ** 15] * n
for i in range(n)[::-1]:
    tmp = dist_y[i] + dist_s[i]
    ans = min(ans, tmp)
    ret[i] -= ans
for i in ret:
    print(i)

Solution (Python):
from heapq import heapify,heappush,heappop

n,m,s,t = map(int,input().split())
adj_list = [[]for i in range(0,(n+1),1,)]
for i in range(0,m,1):
    u,v,a,b = map(int,input().split())
    adj_list[u].append([v,a,b])
    adj_list[v].append([u,a,b])

D_INF = 10**15
d = [D_INF]*(n+1)
d[s] = 0
que = []
heapify(que)
heappush(que,(d[s],s))

while(len(que)):
    time,place = heappop(que)
    if time > d[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d[adj_list[place][i][0]] > time + adj_list[place][i][1]:
            d[adj_list[place][i][0]] = time + adj_list[place][i][1]
            heappush(que,(d[adj_list[place][i][0]],adj_list[place][i][0]))


d_sn = [D_INF]*(n+1)
d_sn[t] = 0
heappush(que,(d_sn[t],t))

while(len(que)):
    time,place = heappop(que)
    if time > d_sn[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d_sn[adj_list[place][i][0]] > time + adj_list[place][i][2]:
             d_sn[adj_list[place][i][0]] = time + adj_list[place][i][2]
             heappush(que,(d_sn[adj_list[place][i][0]],adj_list[place][i][0]))

for i in range(1,n+1,1):
    d[i]=d[i]+d_sn[i]
    heappush(que,(d[i],i))
minimum,minimum_place = heappop(que)

for i in range(0,n,1):
    if minimum_place <= i:
        while(len(que)):
            minimum,minimum_place = heappop(que)
            if minimum_place > i:
                break
    print(10**15-minimum)

Solution (Python):
from heapq import heapify,heappush,heappop

n,m,s,t = map(int,input().split())
adj_list = [[]for i in range(0,(n+1),1,)]
for i in range(0,m,1):
    u,v,a,b = map(int,input().split())
    adj_list[u].append([v,a,b])
    adj_list[v].append([u,a,b])

D_INF = 10**15
d = [D_INF]*(n+1)
d[s] = 0
que = []
heapify(que)
heappush(que,(d[s],s))

while(len(que)):
    time,place = heappop(que)
    if time > d[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d[adj_list[place][i][0]] > time + adj_list[place][i][1]:
            d[adj_list[place][i][0]] = time + adj_list[place][i][1]
            heappush(que,(d[adj_list[place][i][0]],adj_list[place][i][0]))


d_sn = [D_INF]*(n+1)
d_sn[t] = 0
heappush(que,(d_sn[t],t))

while(len(que)):
    time,place = heappop(que)
    if time > d_sn[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d_sn[adj_list[place][i][0]] > time + adj_list[place][i][2]:
             d_sn[adj_list[place][i][0]] = time + adj_list[place][i][2]
             heappush(que,(d_sn[adj_list[place][i][0]],adj_list[place][i][0]))

for i in range(1,n+1,1):
    d[i]=d[i]+d_sn[i]
    heappush(que,(d[i],i))
minimum,minimum_place = heappop(que)

for i in range(0,n,1):
    if minimum_place <= i:
        while(len(que)):
            minimum,minimum_place = heappop(que)
            if minimum_place > i:
                break
    print(10**15-minimum)

Solution (Python):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  
        self._E = 0  
        self._V = V  

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  
                    heapq.heappush(que, (d[e.to], e.to))  
        return d

n,m,s,t=map(int,input().split())
yen=Dijkstra(n)
snuke=Dijkstra(n)
for i in range(0,m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    yen.add(u,v,a)
    yen.add(v,u,a)
    snuke.add(u,v,b)
    snuke.add(v,u,b)

s-=1
t-=1
answer=[]
ye=yen.shortest_path(s)
sn=snuke.shortest_path(t)
cost=float("inf")
for i in range(n-1,-1,-1):
    cost=min(cost,sn[i]+ye[i])
    answer.append(cost)

for i in range(0,len(answer)):
    print(10**15-answer[-i-1])

Solution (Python):
import heapq
n,m,s,t = map(int, input().split())
s -= 1
t -= 1
edges1 = [[] for i in range(n)]
edges2 = [[] for i in range(n)]


for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    
    edges1[u].append((v,a))
    edges1[v].append((u,a))
    
    edges2[u].append((v,b))
    edges2[v].append((u,b))

def dijkstra(N,edges,s):
    q = []
    heapq.heapify(q)
    INF = 10**20

    from datetime import datetime as dt
    x = dt.now()
    cost = [INF] * N
    heapq.heappush(q,(0,s))
    while len(q) > 0:
        c_v,v = heapq.heappop(q)
        
        if cost[v] != INF: continue
        
        
        else: cost[v] = c_v
        for u,c_u in edges[v]:
            if cost[u] != INF:continue
            c_upd = c_v + c_u
            heapq.heappush(q,(c_upd,u))
    
    return cost


cnt1 = dijkstra(n,edges1,s)
cnt2 = dijkstra(n,edges2,t)
zs = [c1+c2 for c1,c2 in zip(cnt1,cnt2)]
mn = 10**20
ans = []
for z in zs[::-1]:
    mn = min(mn,z)
    ans.append(10**15-mn)

for a in ans[::-1]:
    print(a)

Solution (Python):
import heapq
n,m,s,t = map(int, input().split())
s -= 1
t -= 1
edges1 = [[] for i in range(n)]
edges2 = [[] for i in range(n)]


for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    
    edges1[u].append((v,a))
    edges1[v].append((u,a))
    
    edges2[u].append((v,b))
    edges2[v].append((u,b))

def dijkstra(n, edges, s):
    INF = 10**20
    """
    input
        n : 頂点数
        edges : リスト(始点, 終点, コスト)
        s : 始点
    output
        d : 始点からの最短距離
    """
    d = [INF] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelist = []
    
    for v, c in edges[s]:
        
        
        heapq.heappush(edgelist, (c, v))
    
    while len(edgelist):
        
        c_min, v_min = heapq.heappop(edgelist)
        
        if used[v_min]:
            continue
        
        d[v_min] = c_min
        used[v_min] = True
        for v, c in edges[v_min]:
            if not used[v]:
                heapq.heappush(edgelist, (c+c_min, v))
    return d


cnt1 = dijkstra(n,edges1,s)
cnt2 = dijkstra(n,edges2,t)


zs = [c1+c2 for c1,c2 in zip(cnt1,cnt2)]
mn = 10**20
ans = []
for z in zs[::-1]:
    
    mn = min(mn,z)
    ans.append(10**15-mn)

for a in ans[::-1]:
    print(a)

Solution (Python):
import heapq
def dijkstra(G, s):
    dist = [float("inf")]*len(G)
    q = []
    dist[s] = 0
    heapq.heapify(q)
    heapq.heappush(q, [0, s])
    while 0 < len(q):
        pre_cost, p = heapq.heappop(q)
        if dist[p] < pre_cost:
            continue
        for v, d in G[p]:
            if dist[v] > dist[p] + d:
                dist[v] = dist[p] + d
                heapq.heappush(q, [dist[v], v])
    return dist
import sys
input = sys.stdin.readline
def main():
    n, m, s, t = map(int, input().split())
    s, t = s-1, t-1
    G_y = [[] for _ in range(n)]
    G_s = [[] for _ in range(n)]
    f = [True]*n
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G_y[u].append([v, a])
        G_y[v].append([u, a])
        G_s[u].append([v, b])
        G_s[v].append([u, b])
    cost_y = dijkstra(G_y, s)
    cost_s = dijkstra(G_s, t)
    cost = [[cost_y[i] + cost_s[i], i] for i in range(n)]
    cost.sort()
    x = 0
    for i in range(n):
        while not f[cost[x][1]]:
            x += 1
        print(10**15 - cost[x][0])
        f[i] = False

if __name__ == "__main__":
    main()

Solution (Python):






import heapq
def dijkstra(s,path):
    
    d = [float('inf')]*len(path)
    d[s] = 0

    
    q = [(0,s)]
    heapq.heapify(q)

    
    while q:
        c,p = heapq.heappop(q)

        
        if d[p]<c:
            continue

        
        for to,cost in path[p]:
            
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d



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

snuke_path = [[] for i in range(n)]
yen_path = [[] for i in range(n)]

for i in range(m):
    u,v,a,b = map(int, input().split())
    u-=1
    v-=1
    yen_path[u].append([v,a])
    yen_path[v].append([u,a])
    snuke_path[u].append([v,b])
    snuke_path[v].append([u,b])

yen_from_s = dijkstra(s,yen_path)
snuke_to_t = dijkstra(t,snuke_path)

total = [yen_from_s[i]+snuke_to_t[i] for i in range(n)]
ans = [0]*n
ans [-1] = total[-1]
for i in range(n-1):
    ans[-2-i] = min(ans[-1-i],total[-2-i])
ans = [10**15-ans[i] for i in range(n)]

print('\n'.join(map(str,ans)))

Solution (Python):
import sys
from collections import namedtuple
from heapq import heappush, heappop

INF = sys.maxsize

P = namedtuple('P', 'cost v')
Edage = namedtuple('Edge', 'to cost')

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

s, t = s - 1, t - 1


Yen = [[] for _ in range(n)]
Snuuk = [[] for _ in range(n)]

for _ in range(m):
  u, v, a, b = map(int, input().split())
  
  u, v = u - 1, v - 1
  
  Yen[u].append(Edage(v, a))
  Yen[v].append(Edage(u, a))
  Snuuk[u].append(Edage(v, b))
  Snuuk[v].append(Edage(u, b))

  
def min_costs(graph, start):
  costs = [INF] * n
  costs[start] = 0
  
  q = [P(0, start)]
  
  while q:
    cost, v = heappop(q)
    if cost > costs[v]:
      continue
    for to, cost in graph[v]:
      if costs[to] > costs[v] + cost:
        costs[to] = costs[v] + cost
        heappush(q, P(costs[to], to))        
        
  return costs

min_costs_in_yen = min_costs(Yen, s)
min_costs_in_snuuk = min_costs(Snuuk, t)

total_costs = [
  min_costs_in_yen[i] + min_costs_in_snuuk[i] 
  for i in range(n)
]


for i in range(n - 1, 0, -1):
  total_costs[i - 1] = min(total_costs[i - 1], total_costs[i])
                      
    
for i in range(n):
  print(10 ** 15 - total_costs[i])

Solution (Python):
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


n, m, s, t = map(int, input().split())
s -= 1
t -= 1
g_yen = [[] for _ in range(n)]
g_snu = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    
    g_yen[u].append((a, v))
    g_yen[v].append((a, u))
    
    g_snu[u].append((b, v))
    g_snu[v].append((b, u))

d_yen = dijkstra(g_yen, n, s)
d_snu = dijkstra(g_snu, n, t)

d = [d_yen[i] + d_snu[i] for i in range(n)]

ans = [10**15] * n
ans[n - 1] = d[n - 1]
for i in reversed(range(n - 1)):
    ans[i] = min(ans[i + 1], d[i])

for i in range(n):
    ans[i] = 10**15 - ans[i]

print(*ans, sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
egg = [[] for i in range(n)]
es = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  es[u-1].append([a,v-1])
  es[v-1].append([a,u-1]) 
  egg[u-1].append([b,v-1])
  egg[v-1].append([b,u-1]) 

es = tuple(es)
egg = tuple(egg)

import heapq
def dijkstra_heap(s,edge):
    
    d = [10**18] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

ES = dijkstra_heap(s-1,es)
EDGE = dijkstra_heap(t-1,egg)
cost = 0
chk = [0]*n
for i in range(n-1,-1,-1):
  cost = max(cost,10**15-ES[i]-EDGE[i])
  chk[i] = cost
chk = tuple(chk)
print(*chk, sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import heappop, heappush
INF = 10 ** 18

def dijkstra(n, s, g, mode):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for w, *a in g[v]:
            nd = d + a[mode]
            if dist[w] > nd:
                dist[w] = nd
                heappush(hq, (nd, w))
    return dist

def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    graph = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    s_dist = dijkstra(n, s, graph, 0)
    t_dist = dijkstra(n, t, graph, 1)

    cost = float("inf")
    ans = [0] * n
    for i in range(n-1, -1, -1):
        cost = min(cost, s_dist[i] + t_dist[i])
        ans[i] = 10 ** 15 - cost
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,s,t = myinput()
uvab = mylistinput(m)





























import heapq
def dijkstra_heap(n,s,edge):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

g1 = [ [] for _ in range(n) ]
g2 = [ [] for _ in range(n) ]
for i in range(m):
    u = uvab[i][0] - 1
    v = uvab[i][1] - 1
    a = uvab[i][2]
    b = uvab[i][3]
    g1[u].append([a,v])
    g1[v].append([a,u])
    g2[u].append([b,v])
    g2[v].append([b,u])



d1 = dijkstra_heap(n,s-1,g1)
d2 = dijkstra_heap(n,t-1,g2)



yen = 10**15
ans = -1*float("inf")
ls_ans = [0]*n
for i in reversed(range(n)):
    snuke = yen - d1[i] - d2[i] 
    ans = max(ans,snuke)
    ls_ans[i] = ans

for i in range(n):
    print(ls_ans[i])

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,s,t = myinput()
uvab = mylistinput(m)





























import heapq
def dijkstra_heap(n,s,edge):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

g1 = [ [] for _ in range(n) ]
g2 = [ [] for _ in range(n) ]
for i in range(m):
    u = uvab[i][0] - 1
    v = uvab[i][1] - 1
    a = uvab[i][2]
    b = uvab[i][3]
    g1[u].append([a,v])
    g1[v].append([a,u])
    g2[u].append([b,v])
    g2[v].append([b,u])



d1 = dijkstra_heap(n,s-1,g1)
d2 = dijkstra_heap(n,t-1,g2)



yen = 10**15
ans = -1*float("inf")
ls_ans = [0]*n
for i in reversed(range(n)):
    snuke = yen - d1[i] - d2[i] 
    ans = max(ans,snuke)
    ls_ans[i] = ans

for i in range(n):
    print(ls_ans[i])

Solution (Python):
from heapq import heappush, heappop
INF = float("inf")


def Dijkstra(n, s, g, mode):  
    dist = [INF] * n  
    dist[s] = 0  
    hq = [(0, s)]  
    while hq:  
        d, v = heappop(hq)  
        if dist[v] < d:  
            continue
        for w, *a in g[v]:  
            nd = d + a[mode]
            if dist[w] > nd:  
                dist[w] = nd
                heappush(hq, (nd, w))
    return dist


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append((v, a, b))
        g[v].append((u, a, b))

    d_yen = Dijkstra(n, s, g, 0)
    d_sunnk = Dijkstra(n, t, g, 1)

    ans = [0] * n
    cost = float("inf")
    for i in range(n-1, -1, -1):
        cost = min(cost, d_yen[i] + d_sunnk[i])
        ans[i] = 10 ** 15 - cost
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()

Solution (Python):
import heapq

def dijkstra(s, G):
    inf = 1145141919810893
    dist = [inf] * n
    dist[s] = 0
    c = [0] * n
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

n, m, s, t = map(int, input().split())
yen = 10 ** 15
G = [[] for _ in range(n)]
H = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, a])
    G[v].append([u, a])
    H[u].append([v, b])
    H[v].append([u, b])
dist1 = dijkstra(s - 1, G)
dist2 = dijkstra(t - 1, H)
ans = [0] * n
ans[n - 1] = yen - (dist1[n - 1] + dist2[n - 1])
for i in range(n - 2, -1, -1):
    ans[i] = max(ans[i + 1], yen - (dist1[i] + dist2[i]))
for i in ans:
    print(i)

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush

YEN = 10**15
INF = float('inf')


class Graph:
    def __init__(self):
        self.__graph = defaultdict(list)

    def add_edge(self, source, destination, cost):
        self.__graph[source].append((destination, cost))
        self.__graph[destination].append((source, cost))

    @property
    def graph(self):
        return self.__graph


class Dijkstra:
    def __init__(self, graph, source):
        self.__costs = defaultdict(lambda: INF)
        costs = self.__costs
        costs[source] = 0
        g = graph.graph
        q = []
        heappush(q, (costs[source], source))

        while q:
            cp, p = heappop(q)
            if costs[p] < cp:
                continue
            for dst, cost in g[p]:
                alternative = cp + cost
                if costs[dst] > alternative:
                    costs[dst] = alternative
                    heappush(q, (alternative, dst))

    @property
    def costs(self):
        return dict(self.__costs)


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, cost, b = spline()
        g_yen.add_edge(u, v, cost)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s).costs
    d_t = Dijkstra(g_snuuk, t).costs
    costs = [INF] * n
    min_cost = INF
    for i in range(n, 0, -1):
        min_cost = min(min_cost, d_s[i] + d_t[i])
        costs[i - 1] = min_cost
    for cost in costs:
        print(YEN - cost)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush

YEN = 10**15
INF = float('inf')


class Graph:
    def __init__(self):
        self.__graph = defaultdict(list)

    def add_edge(self, source, destination, cost):
        self.__graph[source].append((destination, cost))
        self.__graph[destination].append((source, cost))

    @property
    def graph(self):
        return self.__graph


class Dijkstra:
    def __init__(self, graph, source):
        self.__costs = defaultdict(lambda: INF)
        costs = self.__costs
        costs[source] = 0
        g = graph.graph
        q = []
        heappush(q, (costs[source], source))

        while q:
            cp, p = heappop(q)
            if costs[p] < cp:
                continue
            for dst, cost in g[p]:
                alternative = cp + cost
                if costs[dst] > alternative:
                    costs[dst] = alternative
                    heappush(q, (alternative, dst))

    @property
    def costs(self):
        return self.__costs


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, cost, b = spline()
        g_yen.add_edge(u, v, cost)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s).costs
    d_t = Dijkstra(g_snuuk, t).costs
    costs = [INF] * n
    min_cost = INF
    for i in range(n, 0, -1):
        min_cost = min(min_cost, d_s[i] + d_t[i])
        costs[i - 1] = min_cost
    for cost in costs:
        print(YEN - cost)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush

YEN = 10**15
INF = float('inf')


class Graph:
    def __init__(self):
        self.__graph = defaultdict(list)

    def add_edge(self, source, destination, cost):
        self.__graph[source].append((destination, cost))
        self.__graph[destination].append((source, cost))

    @property
    def graph(self):
        return self.__graph


class Dijkstra:
    def __init__(self, graph, source):
        self.__costs = defaultdict(lambda: INF)
        costs = self.__costs
        costs[source] = 0
        g = graph.graph
        q = []
        heappush(q, (costs[source], source))

        while q:
            cp, p = heappop(q)
            if costs[p] < cp:
                continue
            for dst, cost in g[p]:
                alternative = cp + cost
                if costs[dst] > alternative:
                    costs[dst] = alternative
                    heappush(q, (alternative, dst))

    @property
    def costs(self):
        return self.__costs


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, cost, b = spline()
        g_yen.add_edge(u, v, cost)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s).costs
    d_t = Dijkstra(g_snuuk, t).costs
    costs = [0] * n
    min_cost = INF
    for i in range(n, 0, -1):
        min_cost = min(min_cost, d_s[i] + d_t[i])
        costs[i - 1] = min_cost
    for cost in map(lambda x: YEN - x, costs):
        print(cost)


if __name__ == "__main__":
    main()