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):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappop,heappush
def resolve():
    n,m,s,t=map(int,input().split())
    s-=1; t-=1
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,a))
        E[v].append((u,a))
        R[u].append((v,b))
        R[v].append((u,b))

    
    dist1=[INF]*n
    dist1[s]=0
    Q=[(0,s)]
    while(Q):
        d,v=heappop(Q)
        if(dist1[v]<d): continue
        for nv,w in E[v]:
            if(dist1[nv]>dist1[v]+w):
                dist1[nv]=dist1[v]+w
                heappush(Q,(dist1[nv],nv))

    dist2=[INF]*n
    dist2[t]=0
    Q=[(0,t)]
    while(Q):
        d,v=heappop(Q)
        if(dist2[v]<d): continue
        for nv,w in R[v]:
            if(dist2[nv]>dist2[v]+w):
                dist2[nv]=dist2[v]+w
                heappush(Q,(dist2[nv],nv))

    
    dist=[dist1[v]+dist2[v] for v in range(n)]
    
    for i in range(n-1,0,-1):
        dist[i-1]=min(dist[i-1],dist[i])

    M=10**15
    for v in range(n):
        print(M-dist[v])
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappop,heappush
def resolve():
    n,m,s,t=map(int,input().split())
    s-=1; t-=1
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,a))
        E[v].append((u,a))
        R[u].append((v,b))
        R[v].append((u,b))

    
    dist1=[INF]*n
    dist1[s]=0
    Q=[(0,s)]
    while(Q):
        d,v=heappop(Q)
        if(dist1[v]<d): continue
        for nv,w in E[v]:
            if(dist1[nv]>dist1[v]+w):
                dist1[nv]=dist1[v]+w
                heappush(Q,(dist1[nv],nv))

    dist2=[INF]*n
    dist2[t]=0
    Q=[(0,t)]
    while(Q):
        d,v=heappop(Q)
        if(dist2[v]<d): continue
        for nv,w in R[v]:
            if(dist2[nv]>dist2[v]+w):
                dist2[nv]=dist2[v]+w
                heappush(Q,(dist2[nv],nv))

    
    dist=[dist1[v]+dist2[v] for v in range(n)]
    
    for i in range(n-1,0,-1):
        dist[i-1]=min(dist[i-1],dist[i])

    M=10**15
    for v in range(n):
        print(M-dist[v])
resolve()

Solution (Python):
from collections import defaultdict
G1 = defaultdict(list); G2 = defaultdict(list)
N, M, S, T = map(int, input().split())
S-=1; T-=1
for i in range(M):
    f, t , v1, v2 = map(int, input().split())
    G1[f-1].append((t-1, v1))
    G1[t-1].append((f-1, v1))
    G2[f-1].append((t-1, v2))
    G2[t-1].append((f-1, v2))

import queue
push = queue.heappush
pop = queue.heappop
INF = 10**16
d1 = [INF]*N; d2 = [INF]*N

def dijkstra(s, G, d):
    q = []
    d[s] = 0
    push(q, (0, s))

    while q:
        cost, v = pop(q)
        
        
        if d[v] < cost:
            continue
        for to, tmpcost in G[v]:
            if d[to] > d[v] + tmpcost:
                d[to] = d[v] + tmpcost
                push(q, (d[to], to))

dijkstra(S, G1, d1)
dijkstra(T, G2, d2)
"""
for i in range(N):
    ans = 0
    for j in range(i, N):
        ans = max(ans, 10**15-d1[j]-d2[j])
    print(ans)
"""
anses = [0]*N
ans = 10**15
for i in range(N):
    ans = min(ans, d1[N-1-i]+d2[N-1-i])
    anses[N-1-i]=10**15-ans
for i in range(N):
    print(anses[i])

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

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

uv = [[] for _ in range(n)]
for _ in range(m) :
    u, v, a, b = map(int, input().split())
    uv[u-1].append((v-1, a, b))
    uv[v-1].append((u-1, a, b))
    
q = [(0, s-1)]
ca = [float('inf')] * n
ca[s-1] = 0
while q :
    cco, cur = heappop(q)
    if cco > ca[cur] :
        continue
    for nex, nco, _ in uv[cur] :
        if cco + nco < ca[nex] :
            ca[nex] = cco + nco
            heappush(q, (cco + nco, nex))
            
q = [(0, t-1)]
cb = [float('inf')] * n
cb[t-1] = 0
while q :
    cco, cur = heappop(q)
    if cco > cb[cur] :
        continue
    for nex, _, nco in uv[cur] :
        if cco + nco < cb[nex] :
            cb[nex] = cco + nco
            heappush(q, (cco + nco, nex))

m = [(ca[i] + cb[i], i) for i in range(n)]
m.sort(reverse=True)

for i in range(n) :
    print(10 ** 15 - m[-1][0])
    while m and m[-1][1] <= i :
        m.pop()

Solution (Python):
def dijkstra_heap(n,s,edge,k):
    
    d = [float("inf")] * n
    d[s] = 0
    edgelist = [s]
    while edgelist:
        nextedge = []
        for i in edgelist:
            for j in edge[i]:
                next = j[2]
                c = j[k]
                if d[next] > c + d[i]:
                    d[next] = c + d[i]
                    nextedge.append(next)
        edgelist = nextedge
    return d

def examD():
    N, M, s, t = LI()
    edge = defaultdict(list)

    
    for i in range(M):
        x, y, z1, z2 = map(int, input().split())
        x -=1; y -=1
        edge[x].append((z1,z2,y))
        edge[y].append((z1,z2,x))
    start1 = s-1
    start2 = t-1
    res1 = dijkstra_heap(N,start1, edge,0)
    res2 = dijkstra_heap(N,start2, edge,1)
    ans = []
    snuke = 10**15
    cur = res1[N-1] + res2[N-1]
    ans.append(cur)
    for i in range(N-2,-1,-1):
        if res1[i] + res2[i]<cur:
            cur = res1[i] + res2[i]
            ans.append(cur)
        else:
            ans.append(cur)
    for v in ans[::-1]:
        print(snuke-v)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
def dijkstra_heap(n,s,edge,k):
    
    d = [float("inf")] * n
    used = [True] * n  
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, [e[k],e[2]])
    while edgelist:
        minedge = 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[2]]:
                heappush(edgelist, [e[k] + d[v], e[2]])
    return d

def examD():
    N, M, s, t = LI()
    edge = defaultdict(list)

    
    for i in range(M):
        x, y, z1, z2 = map(int, input().split())
        x -=1; y -=1
        edge[x].append((z1,z2,y))
        edge[y].append((z1,z2,x))
    start1 = s-1
    start2 = t-1
    res1 = dijkstra_heap(N,start1, edge,0)
    res2 = dijkstra_heap(N,start2, edge,1)
    ans = []
    snuke = 10**15
    cur = res1[N-1] + res2[N-1]
    ans.append(snuke-cur)
    for i in range(N-2,-1,-1):
        if res1[i] + res2[i]<cur:
            cur = res1[i] + res2[i]
            ans.append(snuke-cur)
        else:
            ans.append(snuke-cur)
    for v in ans[::-1]:
        print(v)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
def dijkstra_heap(n,s,edge,k):
    
    d = [float("inf")] * n
    used = [True] * n  
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, [e[k],e[2]])
    while edgelist:
        minedge = 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[2]]:
                heappush(edgelist, [e[k] + d[v], e[2]])
    return d

def examD():
    N, M, s, t = LI()
    edge = defaultdict(list)

    
    for i in range(M):
        x, y, z1, z2 = map(int, input().split())
        x -=1; y -=1
        edge[x].append([z1,z2,y])
        edge[y].append([z1,z2,x])
    start1 = s-1
    start2 = t-1
    res1 = dijkstra_heap(N,start1, edge,0)
    res2 = dijkstra_heap(N,start2, edge,1)
    ans = []
    snuke = 10**15
    cur = res1[N-1] + res2[N-1]
    ans.append(snuke-cur)
    for i in range(N-2,-1,-1):
        if res1[i] + res2[i]<cur:
            cur = res1[i] + res2[i]
            ans.append(snuke-cur)
        else:
            ans.append(snuke-cur)
    for v in ans[::-1]:
        print(v)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

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

import heapq as hp

N, M, S, G = map(int, input().split())
graph_y = [[] for _ in range(N)]
graph_s = [[] for _ in range(N)]
for _ in range(M):
    a, b, c, d = map(int, input().split())
    graph_y[a-1].append((c, b-1))
    graph_y[b-1].append((c, a-1))
    graph_s[a-1].append((d, b-1))
    graph_s[b-1].append((d, a-1))

INF = 10**18

def dijkstra(graph, s):
    D = [INF for _ in range(N)] 
    D[s] = 0 
    q = [] 
    hp.heappush(q, (0, s))

    while q:
        nd, np = hp.heappop(q) 
        if D[np] < nd: 
            continue
        for d, p in graph[np]:
            if D[p] > D[np] + d: 
                D[p] = D[np] + d
                hp.heappush(q, (D[p], p))
    
    return D

Ds = dijkstra(graph_y, S-1)
Dg = dijkstra(graph_s, G-1)

ans = [None]*N
ans[N-1] = Ds[N-1] + Dg[N-1]
for n in reversed(range(N-1)):
    ans[n] = min(ans[n+1], Ds[n]+Dg[n])

for a in ans:
    print(10**15-a)

Solution (Python):
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
n, m, s, t = map(int, input().split())
e = dd(list)
money = 10 ** 15
for _ in range(m):
  u, v, a, b = map(int, input().split())
  e[u].append((v, a))
  e[v].append((u, a))
  e[u + n].append((v + n, b))
  e[v + n].append((u + n, b))
"""
for i in range(1, n + 1):
  e[i].append((i + n, 0))
"""
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 15)
      v0 = v // (10 ** 15)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 15) + p[0])
    return d
d = dijkstra(2 * n + 1, e)
x = d.path(s, 2 * n + 1)
y = d.path(t + n, 2 * n + 1)


paths = [float("inf")] * (n + 1)
minpaths = [float("inf")] * (n + 1)
for i in range(1, n + 1):
  paths[i] = x[i] + y[n + i]

minpaths[-1] = paths[-1]
for i in range(n - 1, -1, -1):
  minpaths[i] = min(minpaths[i + 1], paths[i])

for i in range(1, n + 1):
  print(money - minpaths[i])

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


class dijkstra:
    def __init__(self, to, start):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        
        
        self.pq = [(self.dist[start], start)]

    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                
                
                

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

JPY = dijkstra(jpy, s)
JPY.update()
SNUKE = dijkstra(snuke, t)
SNUKE.update()

cost_list = []
cost = inf

for i in range(n)[::-1]:
    cost = min(cost, JPY.dist[i] + SNUKE.dist[i])
    cost_list.append(cost)

cost_list.reverse()
for cost in cost_list:
    ans = pow(10, 15) - cost
    print(ans)

Solution (Python):
from heapq import heappush, heappop
inf = float('inf')
mod = 10**9 + 7

class dijkstra:
    def __init__(self, to, start):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        self.cnt = [0] * self.N
        self.cnt[start] = 1
        self.pq = [(self.dist[start], start)]

    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                if self.dist[nv] == self.dist[v] + w:
                    self.cnt[nv] += self.cnt[v]
                    self.cnt[nv] %= mod

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

JPY = dijkstra(jpy, s)
JPY.update()
SNUKE = dijkstra(snuke, t)
SNUKE.update()

cost_list = []
cost = inf

for i in range(n)[::-1]:
    cost = min(cost, JPY.dist[i] + SNUKE.dist[i])
    cost_list.append(cost)

cost_list.reverse()
for cost in cost_list:
    ans = pow(10, 15) - cost
    print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse.csgraph import dijkstra

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	def dijkstra(E, start):
	    N_d = len(E)
	    dist = [INF] * N_d
	    dist[start] = 0
	    q = [(0, start)]
	    while q:
	        dist_v, v = heappop(q)
	        if dist[v] != dist_v:
	            continue
	        for u, dist_vu in E[v]:
	            dist_u = dist_v + dist_vu
	            if dist_u < dist[u]:
	                dist[u] = dist_u
	                heappush(q, (dist_u, u))
	    return dist

	n, m, s, t = MAP()

	uvab = [LIST() for _ in range(m)]

	A = [[] for _ in range(n+1)]
	B = [[] for _ in range(n+1)]

	for u, v, a, b in uvab:
		A[u].append((v, a))
		A[v].append((u, a))
		B[u].append((v, b))
		B[v].append((u, b))

	distA = dijkstra(A, s)  
	distB = dijkstra(B, t)  

	Ans = []
	init = 10**15
	ans = INF
	for a, b in zip(distA[:0:-1], distB[:0:-1]):
		ans = min(ans, a+b)
		Ans.append(init-ans)
	Ans = Ans[::-1]
	print("\n".join(map(str, Ans)))

main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse.csgraph import dijkstra

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

n, m, s, t = MAP()

uvab = [LIST() for _ in range(m)]

A = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for u, v, a, b in uvab:
	A[u].append((v, a))
	A[v].append((u, a))
	B[u].append((v, b))
	B[v].append((u, b))

distA = dijkstra(A, s)  
distB = dijkstra(B, t)  

Ans = []
init = 10**15
ans = INF
for a, b in zip(distA[:0:-1], distB[:0:-1]):
	ans = min(ans, a+b)
	Ans.append(init-ans)
Ans = Ans[::-1]
print("\n".join(map(str, Ans)))

Solution (Python):
import heapq
import sys

input = sys.stdin.readline
INF = 10**18

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

graph_s = [[] for _ in range(n)]
graph_t = [[] for _ in range(n)]

for e in edge:
    graph_s[e[0]-1].append([e[1]-1,e[2]])
    graph_s[e[1]-1].append([e[0]-1,e[2]])
    graph_t[e[0]-1].append([e[1]-1,e[3]])
    graph_t[e[1]-1].append([e[0]-1,e[3]])

dist_s = [INF]*n
dist_t = [INF]*n

dist_s[s-1] = 0
dist_t[t-1] = 0

heap_s = [[0,s-1]]
heapq.heapify(heap_s)

heap_t = [[0,t-1]]
heapq.heapify(heap_t)

while heap_s:
    cost,node = heapq.heappop(heap_s)
    if dist_s[node] < cost:
        continue
    for adj,adjcost in graph_s[node]:
        if dist_s[node] + adjcost < dist_s[adj]:
            dist_s[adj] = dist_s[node] + adjcost
            heapq.heappush(heap_s,[dist_s[adj],adj])

while heap_t:
    cost,node = heapq.heappop(heap_t)
    if dist_t[node] < cost:
        continue
    for adj,adjcost in graph_t[node]:
        if dist_t[node] + adjcost < dist_t[adj]:
            dist_t[adj] = dist_t[node] + adjcost
            heapq.heappush(heap_t,[dist_t[adj],adj])

dist = INF
ans = []
                                              
for i in range(n):
    dist = min(dist,dist_t[-1-i]+dist_s[-1-i])
    ans.append(10**15-dist)
    
for i in range(n):
    print(ans[-1-i])

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


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    q = [(0, start)]  
    while q:
        dist, pos = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (distance[next_pos], next_pos))
    return distance


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

y_graph = [[] for i in range(n)]
s_graph = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = info[i]
    u -= 1
    v -= 1
    y_graph[u].append((v, a))
    y_graph[v].append((u, a))
    s_graph[u].append((v, b))
    s_graph[v].append((u, b))

s -= 1
t -= 1
y_cost = dijkstra(s, y_graph)
s_cost = dijkstra(t, s_graph)

ans = [0]*n
for i in range(n):
    ans[i] = y_cost[i] + s_cost[i]

for i in range(n-1)[::-1]:
    ans[i] = min(ans[i], ans[i+1])

for num in ans:
    print(10**15 - num)

Solution (Python):

from collections import defaultdict
from heapq import heappop, heappush


class Graph():

    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():

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

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        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):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())



en=Graph()
snu=Graph()

for i in range(m):
    u,v,a,b=map(int,input().split())
    en.add_edge(u,v,a)
    en.add_edge(v,u,a)
    snu.add_edge(u,v,b)
    snu.add_edge(v,u,b)

enen=Dijkstra(en,s)
snusnu=Dijkstra(snu,t)
ans=[enen.shortest_distance(n)+snusnu.shortest_distance(n)]

for i in range(n-1,0,-1):
    d1=enen.shortest_distance(i)
    d2=snusnu.shortest_distance(i)
    ans.append(min(ans[-1],d1+d2))


for i in range(1,n+1):
    print(10**15-ans[-i])

Solution (Python):

from collections import defaultdict
from heapq import heappop, heappush


class Graph():

    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():

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

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        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):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())



en=Graph()
snu=Graph()

for i in range(m):
    u,v,a,b=map(int,input().split())
    en.add_edge(u,v,a)
    en.add_edge(v,u,a)
    snu.add_edge(u,v,b)
    snu.add_edge(v,u,b)

enen=Dijkstra(en,s)
snusnu=Dijkstra(snu,t)
ans=[enen.shortest_distance(n)+snusnu.shortest_distance(n)]

for i in range(n-1,0,-1):
    d1=enen.shortest_distance(i)
    d2=snusnu.shortest_distance(i)
    ans.append(min(ans[-1],d1+d2))


for i in range(1,n+1):
    print(10**15-ans[-i])

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


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0

    
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        if distances[fr] != dist:
            continue

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if distances[to] > new_dist:
                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

    return distances


from_start_yen = dijkstra(G_yen, S)
from_goal_snuuk = dijkstra(G_snuuk, T)

ans = [0] * (N + 1)
for i, yen, snuuk in zip(reversed(range(N)), from_start_yen[::-1], from_goal_snuuk[::-1]):
    ans[i] = max(ans[i + 1], 10 ** 15 - (yen + snuuk))

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

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


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    fixed = [False] * n
    distances[start] = 0

    
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        fixed[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (fixed[to] is False) and (distances[to] > new_dist):
                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

    return distances


from_start_yen = dijkstra(G_yen, S)
from_goal_snuuk = dijkstra(G_snuuk, T)

ans = [0] * (N + 1)
for i, yen, snuuk in zip(reversed(range(N)), from_start_yen[::-1], from_goal_snuuk[::-1]):
    ans[i] = max(ans[i + 1], 10 ** 15 - (yen + snuuk))

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

Solution (Python):
import sys

def main():
    N, M, S, T = map(int, input().split())
    A = [[] for _ in range(N+1)]
    B = [[] for _ in range(N+1)]
    for u, v, a, b in zip(*[iter(map(int, sys.stdin.read().split()))]*4):
        A[u].append((v, a))
        A[v].append((u, a))
        B[u].append((v, b))
        B[v].append((u, b))

    def dijkstra(E, start):
        from heapq import heappush, heappop
        N = len(E)
        inf = float("inf")
        dist = [inf] * N
        dist[start] = 0
        q = [(0, start)]
        while q:
            dist_v, v = heappop(q)
            if dist[v] != dist_v:
                continue
            for u, dist_vu in E[v]:
                dist_u = dist_v + dist_vu
                if dist_u < dist[u]:
                    dist[u] = dist_u
                    heappush(q, (dist_u, u))
        return dist

    dist_A = dijkstra(A, S)
    dist_B = dijkstra(B, T)
    init = 10**15
    Ans = []
    ans = float("inf")
    for a, b in zip(dist_A[:0:-1], dist_B[:0:-1]):
        ans = min(ans, a+b)
        Ans.append(init-ans)
    Ans.reverse()
    print("\n".join(map(str, Ans)))

main()

Solution (Python):
import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())

en=[[]for i in range(n+1)]
sn=[[]for i in range(n+1)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    en[v].append((u,a))
    en[u].append((v,a))
    sn[v].append((u,b))
    sn[u].append((v,b))


import numpy as np
INF=10**20

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    shortest=[INF]*N
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        if d0>shortest[src]:
            continue
        for dst, d1 in paths[src]:
            if d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
    return np.array(shortest)
    
en=dijkstra(s,n+1,en)
sn=dijkstra(t,n+1,sn)

cost=[]
for i in range(1,n+1):
    cost.append(en[i]+sn[i])
cost=cost[::-1]


ans=[]
mi=cost[0]
for i in range(n):
    ans.append(min(mi,cost[i]))
    mi=min(mi,cost[i])
ans=ans[::-1]

for i in ans:
    print(10**15-i)