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
input = sys.stdin.read
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

N,M,S,T, *uvab = map(int,input().split())
graph = [[] for _ in range(N+1)]
for u,v,a,b in zip(*[iter(uvab)]*4):
    graph[u].append((v,a,b))
    graph[v].append((u,a,b))

def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

d1 = np.array(dijkstra(S,0))
d2 = np.array(dijkstra(T,1))

d1 += d2
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]
print('\n'.join(map(str, answer.tolist())))

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

def main():
    N,M,s,t = map(int,input().split())
    INF = 10**15
    
    yedge = [[] for _ in range(N)]
    sedge = [[] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        yedge[u-1].append((a,v-1))
        yedge[v-1].append((a,u-1))
        sedge[u-1].append((b,v-1))
        sedge[v-1].append((b,u-1))
        
    def dij(x,z):
        q = [(0,x)]
        heapq.heapify(q)
        go = [INF for _ in range(N)]
        go[x] = 0
        while q:
            d,now = heapq.heappop(q)
            if go[now] > d:
                continue
            for d,fol in z[now]:
                if go[fol] > go[now]+d:
                    go[fol] = go[now]+d
                    heapq.heappush(q,(go[fol],fol))
        return go
        
    y,s = dij(s-1,yedge),dij(t-1,sedge)
    ans = []
    u = 0
    for i,j in zip(y[::-1],s[::-1]):
        u = max(u,INF-i-j) 
        ans.append(u)
        
    print(*ans[::-1],sep="\n")

if __name__ == "__main__":
    main()

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


INF = sys.maxsize
Edge = namedtuple('Edge', 'to yen snuuk')
Vertex = namedtuple('Vertex', 'cost id')

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

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

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

costs_in_yen = [INF] * (n + 1)
costs_in_snuuk = [INF] * (n + 1)

q = []

heappush(q, Vertex(0, s))
costs_in_yen[s] = 0

while q:
  v = heappop(q)
  if v.cost > costs_in_yen[v.id]:
    continue
  for edge in edges[v.id]:
    if v.cost + edge.yen < costs_in_yen[edge.to]:
      costs_in_yen[edge.to] = v.cost + edge.yen
      heappush(q, Vertex(costs_in_yen[edge.to], edge.to))
      
heappush(q, Vertex(0, t))
costs_in_snuuk[t] = 0

while q:
  v = heappop(q)
  if v.cost > costs_in_snuuk[v.id]:
    continue
  for edge in edges[v.id]:
    if v.cost + edge.snuuk < costs_in_snuuk[edge.to]:
      costs_in_snuuk[edge.to] = v.cost + edge.snuuk
      heappush(q, Vertex(costs_in_snuuk[edge.to], edge.to))      





snuuk_in_hand = [0] * (n + 1)



for i in range(n, 0, -1):  
  
  snuuk_in_hand[i - 1] = max(
    snuuk_in_hand[i],
    
    10**15 - costs_in_yen[i] - costs_in_snuuk[i]
  )

for i in range(0, n):
  print(snuuk_in_hand[i])

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


INF = sys.maxsize
Edge = namedtuple('Edge', 'to yen snuuk')
Vertex = namedtuple('Vertex', 'cost id')

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

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

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

costs_in_yen = [INF] * (n + 1)
costs_in_snuuk = [INF] * (n + 1)

q = []

heappush(q, Vertex(0, s))
costs_in_yen[s] = 0

while q:
  v = heappop(q)
  if v.cost > costs_in_yen[v.id]:
    continue
  for edge in edges[v.id]:
    if v.cost + edge.yen < costs_in_yen[edge.to]:
      costs_in_yen[edge.to] = v.cost + edge.yen
      heappush(q, Vertex(costs_in_yen[edge.to], edge.to))
      
heappush(q, Vertex(0, t))
costs_in_snuuk[t] = 0

while q:
  v = heappop(q)
  if v.cost > costs_in_snuuk[v.id]:
    continue
  for edge in edges[v.id]:
    if v.cost + edge.snuuk < costs_in_snuuk[edge.to]:
      costs_in_snuuk[edge.to] = v.cost + edge.snuuk
      heappush(q, Vertex(costs_in_snuuk[edge.to], edge.to))      


snuuk_in_hand = [0] * (n + 1)

for i in range(n - 1, -1, -1):
  snuuk_in_hand[i] = max(
    snuuk_in_hand[i + 1],
    10**15 - costs_in_yen[i + 1] - costs_in_snuuk[i + 1]
  )

for i in range(0, n):
  print(snuuk_in_hand[i])

Solution (Python):
import sys
input = sys.stdin.readline
n,m,s,t = map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]
gyen = [[] for i in range(n+1)]
gsnu = [[] for i in range(n+1)]
for u,v,a,b in uvab:
  gyen[u].append((v,a))
  gyen[v].append((u,a))
  gsnu[u].append((v,b))
  gsnu[v].append((u,b))
import heapq as hq
def dijkstra(start,graph):
  dist = [10**18]*(n+1)
  dist[start] = 0
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,dd in graph[x]:
      if dist[y] > dist[x]+dd:
        dist[y] = dist[x]+dd
        hq.heappush(q,(dist[y],y))
  return dist
distyen = dijkstra(s,gyen)
distsnu = dijkstra(t,gsnu)
ans = []
for i in range(n,0,-1):
  x = 10**15-(distyen[i]+distsnu[i])
  if i == n:
    ans.append(x)
  else:
    ans.append(max(ans[-1],x))
ans = ans[::-1]
print(*ans,sep="\n")

Solution (Python):
n,m,s,t = map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]
gyen = [[] for i in range(n+1)]
gsnu = [[] for i in range(n+1)]
for u,v,a,b in uvab:
  gyen[u].append((v,a))
  gyen[v].append((u,a))
  gsnu[u].append((v,b))
  gsnu[v].append((u,b))
import heapq as hq
def dijkstra(start,graph):
  dist = [10**18]*(n+1)
  dist[start] = 0
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,dd in graph[x]:
      if dist[y] > dist[x]+dd:
        dist[y] = dist[x]+dd
        hq.heappush(q,(dist[y],y))
  return dist
distyen = dijkstra(s,gyen)
distsnu = dijkstra(t,gsnu)
ans = []
for i in range(n,0,-1):
  x = 10**15-(distyen[i]+distsnu[i])
  if i == n:
    ans.append(x)
  else:
    ans.append(max(ans[-1],x))
ans = ans[::-1]
print(*ans,sep="\n")

Solution (Python):
inf = 1145141919810364364
start = 10**15
import heapq

def di(s,fl):
    d = [inf] * n
    used = [1] * n
    d[s] = 0
    used[s] = 0
    lis = []
    
    for a,b in edge[fl][s]:
        heapq.heappush(lis,a*(10**6)+b)
        
    while lis:
        minedge = heapq.heappop(lis)
        
        if used[minedge%(10**6)] == 0:
            continue

        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = 0

        for q in edge[fl][v]:
            if used[q[1]] == 1:
                heapq.heappush(lis,(q[0]+d[v])*(10**6)+q[1])
    return d

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

edge = [[[] for i in range(n)] for _ in range(2)]

for i in range(m):
    u,v,a,b = map(int,input().split())
    edge[0][u-1].append([a,v-1])
    edge[0][v-1].append([a,u-1])
    edge[1][u-1].append([b,v-1])
    edge[1][v-1].append([b,u-1])
    
a = di(s-1,0)
b = di(t-1,1)
k = start - a[n-1] - b[n-1]
ans = [0] * n

for i in range(n):
    k = max(k , start - (a[n-1-i] + b[n-1-i]))
    ans[n-1-i] = k
    
for i in range(n):
    print(ans[i])

Solution (Python):
import heapq
import sys
input=sys.stdin.readline
def dijk(s,edge,n):
    used = [-1] * n 
    used[s] = 0
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if used[minedge[1]]>=0:
            continue
        v = minedge[1]
        kai=minedge[0]
        used[v] = kai
        for e in edge[v]:
            if used[e[1]]==-1:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used


def main():
    n,m,s,t = map(int,input().split()) 
    s-=1
    t-=1
    edge1 = [[] for i in range(n)]
    edge2= [[] for i in range(n)]
    
    for i in range(m):
        x,y,z,w = map(int,input().split())
        edge1[x-1].append([z,y-1])
        edge1[y-1].append([z,x-1])
        edge2[x-1].append([w,y-1])
        edge2[y-1].append([w,x-1])
    en=dijk(s,edge1,n)
    su=dijk(t,edge2,n)
    ans=[]
    aa=10**20
    for i in range(n-1,-1,-1):
        aa=min(aa,en[i]+su[i])
        ans.append(10**15-aa)
    for i in range(n-1,-1,-1):
        print(ans[i])
if __name__=='__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
 
s -= 1
t -= 1
 


 




 




 
M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2], C[i][3]])  
    M[C[i][1]-1].append([C[i][0]-1, C[i][2], C[i][3]])  
 
import heapq

def dijkstra(a, in_connect_list, v, money_kind): 
    out_shortest_list = [10**15 for i in range(v)]
    out_shortest_list[a] = 0
    searching_list = [a]
    
    while searching_list != []:
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                c = j[0]
                p = j[money_kind] 
                if out_shortest_list[c] > p + out_shortest_list[i]:
                    out_shortest_list[c] = p + out_shortest_list[i]
                    new_search_list.append(c)
        searching_list = list(set(new_search_list))  
    return out_shortest_list
 


 
Ds = dijkstra(s, M, n, 1)
Dt = dijkstra(t, M, n, 2)
 
ANS = [0] * n
 

 
ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans
 
for i in range(n):
    print(10**15 - ANS[i])

Solution (Python):
import sys
import heapq
input=sys.stdin.readline
def dijkstra_heap(s,edge):
    
    d = [float("inf")] * 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
n,m,s,t=map(int,input().split())
ey=[[] for _ in range(n)]
es=[[] for _ in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  ey[u-1].append([a,v-1])
  ey[v-1].append([a,u-1])
  es[u-1].append([b,v-1])
  es[v-1].append([b,u-1])
dy=dijkstra_heap(s-1,ey)
ds=dijkstra_heap(t-1,es)
accumb=[10*10]*n
accumb[n-1]=int(dy[n-1]+ds[n-1])
for i in range(1,n):
  accumb[n-i-1]=int(min(dy[n-i-1]+ds[n-i-1],accumb[n-i]))
money=10**15
for i in range(n):
  print(money-accumb[i])

Solution (Python):



import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1














M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2], C[i][3]])  
    M[C[i][1]-1].append([C[i][0]-1, C[i][2], C[i][3]])  

import heapq





























def dijkstra(a,in_connect_list,v,money_kind):
 
    out_shortest_list = [10**15 for i in range(v)]
    out_shortest_list[a] = 0
    searching_list = [a]
    
    while searching_list != []:
    
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                c = j[0]
                p = j[money_kind] 
                if out_shortest_list[c] > p + out_shortest_list[i]:
                    out_shortest_list[c] = p + out_shortest_list[i]
                    new_search_list.append(j[0])
        searching_list = new_search_list
 
    return out_shortest_list




Ds = dijkstra(s, M, n, 1)
Dt = dijkstra(t, M, n, 2)

ANS = [0] * n



ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])

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

def dijkstra(n, start, edge):
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist
    
n, m, s, t = map(int, input().split())
G_yen = [[] for _ in range(n+1)]
G_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G_yen[u].append((v, a))
    G_yen[v].append((u, a))
    G_snuuk[u].append((v, b))
    G_snuuk[v].append((u, b))
dijk_yen = dijkstra(n+1, s, G_yen)
dijk_snuuk = dijkstra(n+1, t, G_snuuk)
L = []
U = 10**15
now = U
for i in range(n, 0, -1):
    now = min(now, dijk_yen[i]+dijk_snuuk[i])
    L.append(U-now)
print(*L[::-1], sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1




M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  
    M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  

N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  
    N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  

import heapq

def dijkstra(s, M):
    D = [10**16] * n  
    P = [-1] * n  
    D[s] = 0
    V = [0] * n  
    Q = []  
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])
    return D, P

Ds, _ = dijkstra(s, M)
Dt, _ = dijkstra(t, N)

ANS = [0] * n



ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])

Solution (Python):
import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
 
s -= 1
t -= 1
 


 
M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  
    M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  
 
N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  
    N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  
 
import heapq
 
def dijkstra(s, M):
    D = [10**16] * n  
    P = [-1] * n  
    D[s] = 0
    V = [0] * n  
    Q = []  
    for v in range(n):
        heapq.heappush(Q, [D[v], v])
 
    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])
    return D, P
 
Ds, _ = dijkstra(s, M)
Dt, _ = dijkstra(t, N)
 
ANS = [0] * n
 

 
ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans
 
for i in range(n):
    print(10**15 - ANS[i])

Solution (Python):
import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1








M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  
    M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  

N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  
    N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  

import heapq

def dijkstra(s, M):
    D = [10**16] * n  
    P = [-1] * n  
    D[s] = 0
    V = [0] * n  
    Q = []  
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])
    return D, P

Ds, _ = dijkstra(s, M)
Dt, _ = dijkstra(t, N)

ANS = [0] * n



ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])

Solution (Python):
import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1




M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  
    M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  

N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  
    N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  

import heapq

def dijkstra(s, M):
    D = [10**16] * n  
    P = [-1] * n  
    D[s] = 0
    V = [0] * n  
    Q = []  
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])
    return D, P

Ds, _ = dijkstra(s, M)
Dt, _ = dijkstra(t, N)

ANS = [0] * n



ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])

Solution (Python):
from heapq import heappush,heappop,heapify
INF=10**18
def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for v,c in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist
 
n,m,s,t=map(int,input().split())  
s,t=s-1,t-1
enG=[[] for i in range(n)]
snG=[[] for i in range(n)]

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

enc=dijkstra(enG,s,n)
snc=dijkstra(snG,t,n)
res=[(enc[i]+snc[i],i) for i in range(n)]
heapify(res)
for i in range(n):
    while(res[0][1]<i):
        heappop(res)
    print(10**15-res[0][0])

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


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

for i in range(m):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

for i in range(m):
    c[a[i][0]-1].append((a[i][1]-1,a[i][3]))
    c[a[i][1]-1].append((a[i][0]-1,a[i][3]))

from heapq import heappush, heappop

def dijkstra(edges, size, source):
    
    
    
    INF=pow(10,15)
    distance = [INF] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

x=dijkstra(b,n,s-1)
y=dijkstra(c,n,t-1)
ans=[0]*n
w=pow(10,15)
for i in range(n):
    v=x[n-1-i]+y[n-1-i]
    w=min(v,w)
    ans[n-1-i]=w

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

Solution (Python):
n,m,s,t= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)] 
c = [[] for i in range(n)] 

for i in range(m):
    b[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    b[a[i][1]-1].append((a[i][0]-1,a[i][2]))

for i in range(m):
    c[a[i][0]-1].append((a[i][1]-1,a[i][3]))
    c[a[i][1]-1].append((a[i][0]-1,a[i][3]))

from heapq import heappush, heappop

def dijkstra(edges, size, source):
    
    
    
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

x=dijkstra(b,n,s-1)
y=dijkstra(c,n,t-1)
ans=[0]*n
w=float('inf')
for i in range(n):
    v=x[n-1-i]+y[n-1-i]
    w=min(v,w)
    ans[n-1-i]=w

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import fractions
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


def dijkstra(graph, start, n):
    h = []
    heapq.heappush(h, (0, start))
    costs = [INF for _ in range(n)]
    while h:
        cost, cur = heapq.heappop(h)
        if costs[cur] != INF:
            continue
        costs[cur] = cost
        for edge in graph[cur]:
            ecost, tgt = edge
            if costs[tgt] == INF:
                heapq.heappush(h, (cost + ecost, tgt))

    return costs


def main():
    money = 10 ** 15
    n, m, s, t = getlist()
    s -= 1; t -= 1

    yengraph = [[] for _ in range(n)]
    snuukgraph = [[] for _ in range(n)]
    for i in range(m):
        a, b, c, d = getlist()
        a -= 1; b -= 1
        yengraph[a].append([c, b])
        yengraph[b].append([c, a])
        snuukgraph[a].append([d, b])
        snuukgraph[b].append([d, a])

    ycost = dijkstra(yengraph, s, n)
    scost = dijkstra(snuukgraph, t, n)

    sumcost = []
    idx = 1
    for y, s in zip(ycost, scost):
        sumcost.append((y+s, idx))
        idx += 1
    sumcost.sort()
    idx = 0
    for i in range(n):
        while True:
            ans, cid = sumcost[idx]
            if cid > i:
                print(money - ans)
                break
            else:
                idx += 1
    
    
    


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import heapq
n,m,s,t = inm()
dst = [{} for i in range(n)]
for i in range(m):
    u,v,a,b = inm()
    dst[u-1][v-1] = (a,b)
    dst[v-1][u-1] = (a,b)

costa = [BIG]*n
costb = [BIG]*n
q = [(0,s-1)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if costa[p]<=d:
        continue
    costa[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v][0], v))

q = [(0,t-1)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if costb[p]<=d:
        continue
    costb[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v][1], v))




mn = BIG
ans = []
for i in range(n-1,-1,-1):
    mn = min(mn, costa[i]+costb[i])
    ans.append(mn)
for i in range(n-1,-1,-1):
    print(10**15-ans[i])

Solution (Python):
from heapq import *
from itertools import *


def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D


n, m, s, t, *L = map(int, open(0).read().split())
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for u, v, a, b in zip(*[iter(L)] * 4):
	u -= 1
	v -= 1
	yen[u].append((v, a))
	yen[v].append((u, a))
	snuuk[u].append((v, b))
	snuuk[v].append((u, b))
stoi = Dijkstra(yen, s - 1)
ttoi = Dijkstra(snuuk, t - 1)
rest = [10 ** 15 - x - y for x, y in zip(stoi, ttoi)]
ans = list(accumulate(rest[::-1], max))[::-1]
print(*ans)

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')
ycost = [INF] * N
ycost[S] = 0
q = [(0,S)]
heapq.heapify(q)
while q:
    c,v = heapq.heappop(q)
    for to,a,b in es[v]:
        if c+a >= ycost[to]: continue
        ycost[to] = c+a
        heapq.heappush(q, (c+a,to))

scost = [INF] * N
scost[T] = 0
q = [(0,T)]
heapq.heapify(q)
while q:
    c,v = heapq.heappop(q)
    for to,a,b in es[v]:
        if c+b >= scost[to]: continue
        scost[to] = c+b
        heapq.heappush(q, (c+b,to))

a = 0
ans = []
for y,s in zip(ycost[::-1],scost[::-1]):
    tmp = 10**15 -y -s
    a = max(a, tmp)
    ans.append(a)
print(*ans[::-1], sep='\n')

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, s, t = map(int, input().split())
e = dd(list)
ee = dd(list)
for i in range(M):
  u, v, a, b = map(int, input().split())
  e[u].append((v, a))
  e[v].append((u, a))
  ee[u].append((v, b))
  ee[v].append((u, b))

import heapq
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 ** 10)
      v0 = v // (10 ** 10)
      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 ** 10) + p[0])
    return d
dij = dijkstra(N, e)
edij = dijkstra(N, ee)
p = dij.path(s, 0)
revp = edij.path(t, 0)
mny = pow(10, 15)
table = [0] * (N + 1)
for x in range(1, N + 1):
  table[x] = mny - p[x] - revp[x]
csmx = [0] * (N + 1)

for i in range(N, 0, -1): csmx[i - 1] = max(csmx[i - 1], table[i], csmx[i])
for i in range(N): print(csmx[i])

Solution (Python):
import heapq as hq
from collections import defaultdict
n, m, s, t = map(int,input().split())
s -= 1
t -= 1
edges = defaultdict(list)
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edges[u-1].append((v-1, a, b))
    edges[v-1].append((u-1, a, b))
INF = float("inf")
d = [INF]*n
d[s] = 0
q = [(0,s)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, a, b in edges[i]:
        if d[j] > d[i]+a:
            d[j] = d[i]+a
            hq.heappush(q, (d[j], j))
ttoi = [INF]*n
ttoi[t] = 0
q = [(0,t)]
while q:
    dist, i = hq.heappop(q)
    if ttoi[i] < dist:
        continue
    for j, a, b in edges[i]:
        if ttoi[j] > ttoi[i]+b:
            ttoi[j] = ttoi[i]+b
            hq.heappush(q, (ttoi[j], j))
tmp = INF
ans = [None]*n
for i in range(n-1,-1,-1):
    if d[i]+ttoi[i] < tmp:
        tmp = d[i]+ttoi[i]
    ans[i] = 10**15-tmp
print(*ans, sep="\n")