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

    def minimum_cost(self, destination):
        return self.__costs[destination]


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)
    d_t = Dijkstra(g_snuuk, t)
    costs = [0] * n
    costs[-1] = YEN - d_s.minimum_cost(n) - d_t.minimum_cost(n)
    for i in range(n - 2, -1, -1):
        cost = YEN - d_s.minimum_cost(i + 1) - d_t.minimum_cost(i + 1)
        costs[i] = max(cost, costs[i + 1])
    for cost in costs:
        print(cost)


if __name__ == "__main__":
    main()

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


class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


def main():

    N, M, s, t = map(int, input().split())
    s, t = s - 1, t - 1
    G = [{} for _ in range(N)]

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

    
    ans = [0] * N
    
    
    q = PriorityQueue([(0, s)])  
    vis = [False] * N
    while len(q):
        c, v = q.pop()
        if vis[v] is True:
            continue
        ans[v] = c
        vis[v] = True
        for n in G[v].keys():
            if vis[n] is True:
                continue
            q.push((c + G[v][n][0], n))    
    
    q = PriorityQueue([(0, t)])  
    vis = [False] * N
    while len(q):
        c, v = q.pop()
        if vis[v] is True:
            continue
        ans[v] += c
        vis[v] = True
        for n in G[v].keys():
            if vis[n] is True:
                continue
            q.push((c + G[v][n][1], n))    

    
    MONEY = pow(10, 15)
    for i in range(1, N):
        if ans[N - i] < ans[N - i - 1]:
            ans[N - i - 1] = ans[N - i]
    print('\n'.join(map(lambda x: str(MONEY - x), ans)))


if __name__ == '__main__':
    main()

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

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


links_e = [[] for _ in range(n+1)]
links_s = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    links_e[u].append((a,v))
    links_e[v].append((a,u))
    links_s[u].append((b,v))
    links_s[v].append((b,u))


import heapq
def dijkstra(links, start, n):
    inf = 10**10
    d = [inf] * (n+1)
    d[start] = 0
    hq = []
    used = set()
    used.add(start)
    for i in links[start]:
        heapq.heappush(hq, i)
    while(hq):
        cost,i = heapq.heappop(hq)
        if( i in used):
            continue
        d[i] = cost
        used.add(i)
        for tmp in links[i]:
            cost_next, j = tmp
            if(not j in used):
                heapq.heappush(hq, (cost+cost_next, j))
    return d

d_e = dijkstra(links_e, s, n)
d_s = dijkstra(links_s, t, n)

ans = [0] * (n+1)
min_cost = 10**15
for i in range(n,0,-1):
    min_cost = min(min_cost, d_e[i]+d_s[i])
    ans[i] = min_cost

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

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

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


links_e = [[] for _ in range(n+1)]
links_s = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    links_e[u].append((a,v))
    links_e[v].append((a,u))
    links_s[u].append((b,v))
    links_s[v].append((b,u))


import heapq
def dijkstra(links, start, n):
    inf = 10**10
    d = [inf] * (n+1)
    d[start] = 0
    hq = []
    used = set()
    used.add(start)
    for i in links[start]:
        heapq.heappush(hq, i)
    while(hq):
        cost,i = heapq.heappop(hq)
        if( i in used):
            continue
        d[i] = cost
        used.add(i)
        for tmp in links[i]:
            cost_next, j = tmp
            if(not j in used):
                heapq.heappush(hq, (cost+cost_next, j))
    return d

d_e = dijkstra(links_e, s, n)
d_s = dijkstra(links_s, t, n)

ans = [0] * (n+1)
min_cost = 10**15
for i in range(n,0,-1):
    min_cost = min(min_cost, d_e[i]+d_s[i])
    ans[i] = min_cost

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

Solution (Python):




import heapq

def dijkstra(n:int,graph,s):
    
    
    
    
    d = [float('inf')] * n  
    notvisited = [True] * n 
    vertex_list = []        

    
    d[s] = 0
    notvisited[s] = False
    [heapq.heappush(vertex_list,v) for v in graph[s]] 

    while len(vertex_list):
        minedge = heapq.heappop(vertex_list) 
        vertex = minedge[1]
        if notvisited[vertex]:
            d[vertex] = minedge[0]
            notvisited[vertex] = False 

            
            for e in graph[vertex]: 
                next_vertex = e[1]
                if notvisited[next_vertex]:
                    heapq.heappush(vertex_list,(d[vertex]+e[0],next_vertex)) 
    
    return d



n,m,s,t = map(int,input().split())
graph_a = {x:[] for x in range(n)}
graph_b = {x:[] for x in range(n)}
money = 10**15

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

d_a = dijkstra(n,graph_a,s-1) 
d_b = dijkstra(n,graph_b,t-1) 

min_list = [float('inf')] * n 
min_list[0] = d_a[-1] + d_b[-1]
for i in range(1,n):
    x = d_a[n-i-1] + d_b[n-i-1]
    if x < min_list[i-1]:
        min_list[i] = x
    else:
        min_list[i] = min_list[i-1]

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

Solution (Python):
from heapq import heappop,heappush

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())
    G[u-1].append({"to":v-1, "yen":a, "snuuk":b})
    G[v-1].append({"to":u-1, "yen":a, "snuuk":b})

def dijkstra(sta:int, how:str):
    """
    頂点staから各頂点への最小コスト
    how: "yen" or "snuuk"
    """
    cost = [float("inf")] * N
    cost[sta] = 0
    que = [(0, sta)]

    while que:
        c,v = heappop(que)
        if cost[v] < c: continue
        for e in G[v]:
            if cost[e["to"]] > cost[v] + e[how]:
                cost[e["to"]] = cost[v] + e[how]
                heappush(que, (cost[e["to"]], e["to"]))
    
    return cost


snuuk = dijkstra(T, "snuuk")

yen = dijkstra(S, "yen")

cost = [s + y for s,y in zip(snuuk,yen)]

ans = []
MINCOST = float("inf")
for year in range(N - 1, -1 ,-1):
    MINCOST = min(MINCOST, cost[year])
    ans.append(10 ** 15 - MINCOST)

print(*reversed(ans),sep="\n")

Solution (Python):
from heapq import heappop, heappush

N, M, S, T = map(int, input().split())
K = 10**15
S -= 1
T -= 1

edgesYen = [[] for _ in range(N)]
edgesSun = [[] for _ in range(N)]

for _ in range(M):
    fr, to, yen, sun = map(int, input().split())
    fr -= 1
    to -= 1
    edgesYen[fr].append((to, yen))
    edgesYen[to].append((fr, yen))
    edgesSun[fr].append((to, sun))
    edgesSun[to].append((fr, sun))

def calcMinDist(edges, start):
    minDist = [10**18] * N
    minDist[start] = 0
    que = [(0, start)]
    while que:
        dist, now = heappop(que)

        if minDist[now] < dist:
            continue

        for to, d in edges[now]:
            if minDist[to] > dist + d:
                heappush(que, (dist + d, to))
                minDist[to] = dist + d

    return minDist

minDistYenS = calcMinDist(edgesYen, S)
minDistSunT = calcMinDist(edgesSun, T)

ans = [0] * N
for mid in range(N):
    ans[mid] = K - minDistYenS[mid] - minDistSunT[mid]

for mid in range(N - 1)[::-1]:
    ans[mid] = max(ans[mid], ans[mid + 1])

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

Solution (Python):
from heapq import heappop, heappush

N, M, S, T = map(int, input().split())
K = 10**15
S -= 1
T -= 1

edgesYen = [[] for _ in range(N)]
edgesSun = [[] for _ in range(N)]

for _ in range(M):
    fr, to, yen, sun = map(int, input().split())
    fr -= 1
    to -= 1
    edgesYen[fr].append((to, yen))
    edgesYen[to].append((fr, yen))
    edgesSun[fr].append((to, sun))
    edgesSun[to].append((fr, sun))

def calcMinDist(edges, start):
    minDist = [10**18] * N
    minDist[start] = 0
    que = [(0, start)]
    while que:
        dist, now = heappop(que)

        if minDist[now] < dist:
            continue

        for to, d in edges[now]:
            if minDist[to] > dist + d:
                heappush(que, (dist + d, to))
                minDist[to] = dist + d

    return minDist

minDistYenS = calcMinDist(edgesYen, S)
minDistSunT = calcMinDist(edgesSun, T)

ans = [0] * N
for mid in range(N):
    ans[mid] = K - minDistYenS[mid] - minDistSunT[mid]

for mid in range(N - 1)[::-1]:
    ans[mid] = max(ans[mid], ans[mid + 1])

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

Solution (Python):

from collections import defaultdict
from heapq import heappop, heappush
import sys
input=sys.stdin.readline

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]

ga=Graph()
gb=Graph()
n,m,s,t=map(int,input().split())
for _ in range(m):
    u,v,a,b=map(int,input().split())
    ga.add_edge(u,v,a)
    ga.add_edge(v,u,a)
    gb.add_edge(u,v,b)
    gb.add_edge(v,u,b)

da = Dijkstra(ga,s)
db = Dijkstra(gb,t)
x=[]
for i in range(1,n+1):
    x.append(da.shortest_distance(i)+db.shortest_distance(i))
for i in range(n-2,-1,-1):
    x[i]=min(x[i],x[i+1])
for i in range(n):
    print(10**15-x[i])

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

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

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((v, a))
    G_y[v].append((u, a))
    G_s[u].append((v, b))
    G_s[v].append((u, b))
dist_y = dijkstra(G_y, n+1, s)
dist_s = dijkstra(G_s, n+1, t)
ans = [0] * n
prev = 0
for i in range(1, n+1)[::-1]:
    amount = 10**15 - (dist_y[i] + dist_s[i])
    prev = max(prev, amount)
    ans[i-1] = prev
print(*ans, sep='\n')

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')
dy = [INF]*N
dy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    d,v = heapq.heappop(hq)
    for to,a,_ in es[v]:
        if d+a >= dy[to]: continue
        dy[to] = d+a
        heapq.heappush(hq, (d+a, to))
ds = [INF]*N
ds[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    d,v = heapq.heappop(hq)
    for to,_,a in es[v]:
        if d+a >= ds[to]: continue
        ds[to] = d+a
        heapq.heappush(hq, (d+a, to))

ans = []
m = 0
for y,s in reversed(list(zip(dy,ds))):
    m = max(m, 10**15-y-s)
    ans.append(m)
ans.reverse()
print(*ans, sep='\n')

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    for i in range(m):
        x,y,a,b = LI()
        x -= 1
        y -= 1
        v[x].append((y,a,b))
        v[y].append((x,a,b))
    d = [float("inf")]*n
    d[s] = 0
    q = [(0,s)]
    while q:
        dx,x = heappop(q)
        if d[x] < dx:
            continue
        for y,a,b in v[x]:
            nd = dx+a
            if nd < d[y]:
                d[y] = nd
                heappush(q,(nd,y))
    c = [float("inf")]*n
    c[t] = 0
    q = [(0,t)]
    while q:
        cx,x = heappop(q)
        if c[x] < cx:
            continue
        for y,a,b in v[x]:
            nc = cx+b
            if nc < c[y]:
                c[y] = nc
                heappush(q,(nc,y))
    s = float("inf")
    N = 10**15
    ans = []
    for i in range(n)[::-1]:
        s = min(s,d[i]+c[i])
        ans.append(N-s)
    for i in ans[::-1]:
        print(i)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
from heapq import heappush, heappop
from itertools import accumulate
def dijkstra(s,n,dic):
  q = [(0,s)]
  dist = [10**20]*n
  dist[s] = 0
  while q:
    v,p = heappop(q)
    if dist[p]<v:
      continue
    for e,c in dic[p]:
      if dist[e]>dist[p]+c:
        dist[e] = dist[p]+c
        heappush(q,(dist[e],e))
  return dist
N,M,s,t,*L = map(int, open(0).read().split())
Els = [[] for i in range(N+1)]
yEls = [[] for i in range(N+1)]
sEls = [[] for i in range(N+1)]
for u,v,a,b in zip(*[iter(L)]*4):
  sEls[u].append((v,b))
  sEls[v].append((u,b))
  yEls[u].append((v,a))
  yEls[v].append((u,a))

ydist = dijkstra(s,N+1,yEls)
sdist = dijkstra(t,N+1,sEls)
ls = list(accumulate((ydist[i]+sdist[i] for i in range(N,0,-1)),min))
for i in range(N-1,-1,-1):
  print(10**15-ls[i])

Solution (Python):


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


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

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

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

d_yen = dijkstra_heap(s,edge_yen)
d_snuke = dijkstra_heap(t,edge_snuke)
ans = [0]*(n)
m = float("inf")
for i in range(n,0,-1):
  m = min(d_yen[i]+d_snuke[i],m)
  ans[i-1]=10**15-m
print(*ans,sep='\n')

Solution (Python):


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


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

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

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

d_yen = dijkstra_heap(s,edge_yen)
d_snuke = dijkstra_heap(t,edge_snuke)
ans = [0]*(n)
m = float("inf")
for i in range(n,0,-1):
  m = min(d_yen[i]+d_snuke[i],m)
  ans[i-1]=10**15-m
print(*ans,sep='\n')

Solution (Python):
import bisect
import collections
import heapq
from collections import defaultdict
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


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

MAX_VAL = 10 ** 20
uvab = llmi(m)
jpy_cost = defaultdict(dict)
snuke_cost = defaultdict(dict)


def dijkstra2_scipy(adj, start, n=None, limit=None):
    """
    caution!  add 10**-10 to avoid 0 cost
    """
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph._shortest_path import dijkstra
    if limit:
        limit += 0.5
    cost, row_ind, col_ind = [], [], []
    for k1, _v in adj.items():
        for k2, _cost in _v.items():
            row_ind.append(k1)
            col_ind.append(k2)
            cost.append(_cost + 10 ** -10)
    cost_matrix = csr_matrix((cost, (row_ind, col_ind)))
    return dijkstra(cost_matrix, indices=[start])[0]


def dijkstra2(adj, start, n):
    MAX_VAL = float('inf')
    INF = MAX_VAL
    dist = [INF for _ in range(n)]
    dist[start] = 0
    pq = []
    heapq.heappush(pq, [dist[start], start])
    while pq:
        u_dist, u_id = heapq.heappop(pq)  
        if u_dist == dist[u_id]:
            for v in adj[u_id]:
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v]:
                    dist[v] = dist[u_id] + w_uv
                    heapq.heappush(pq, [dist[v], v])
    return dist


for u, v, a, b in uvab:
    u = u - 1
    v = v - 1
    jpy_cost[u][v] = a
    jpy_cost[v][u] = a
    snuke_cost[u][v] = b
    snuke_cost[v][u] = b

jpy_dijk = dijkstra2(jpy_cost, start=s - 1, n=n)
snuke_dijk = dijkstra2(snuke_cost, start=t - 1, n=n)
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    
    val = jpy_dijk[i] + snuke_dijk[i]
    assert val < MAX_VAL
    min_val = min(min_val, val)
    res.append(min_val)
for x in reversed(res):
    print(10 ** 15 - int(x))

Solution (Python):
import bisect
import collections
import heapq
from collections import defaultdict
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


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

MAX_VAL = 10 ** 20
uvab = llmi(m)
jpy_cost = defaultdict(dict)
snuke_cost = defaultdict(dict)


def dijkstra2_scipy(adj, start, n=None, limit=None):
    """
    caution!  add 10**-10 to avoid 0 cost
    """
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph._shortest_path import dijkstra
    if limit:
        limit += 0.5
    cost, row_ind, col_ind = [], [], []
    for k1, _v in adj.items():
        for k2, _cost in _v.items():
            row_ind.append(k1)
            col_ind.append(k2)
            cost.append(_cost + 10 ** -10)
    cost_matrix = csr_matrix((cost, (row_ind, col_ind)))
    return dijkstra(cost_matrix, indices=[start])[0]


def dijkstra2(adj, start, n):
    MAX_VAL = float('inf')
    INF = MAX_VAL
    dist = [INF for _ in range(n)]
    dist[start] = 0
    pq = []
    heapq.heappush(pq, [dist[start], start])
    while pq:
        u_dist, u_id = heapq.heappop(pq)  
        if u_dist == dist[u_id]:
            for v in adj[u_id]:
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v]:
                    dist[v] = dist[u_id] + w_uv
                    heapq.heappush(pq, [dist[v], v])
    return dist


for u, v, a, b in uvab:
    u = u - 1
    v = v - 1
    jpy_cost[u][v] = a
    jpy_cost[v][u] = a
    snuke_cost[u][v] = b
    snuke_cost[v][u] = b

jpy_dijk = dijkstra2(jpy_cost, start=s - 1, n=n)
snuke_dijk = dijkstra2(snuke_cost, start=t - 1, n=n)
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    
    val = jpy_dijk[i] + snuke_dijk[i]
    assert val < MAX_VAL
    min_val = min(min_val, val)
    res.append(min_val)
for x in reversed(res):
    print(10 ** 15 - int(x))

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

input = sys.stdin.readline

def Dijkstra_heap(s, edge):
    d = [10 ** 20] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelst = []
    for i, j in edge[s]:
        heappush(edgelst, i+j*(10**6))
    while edgelst:
        edgemin = heappop(edgelst)
        v = edgemin % (10**6)
        if used[v]: continue
        d[v] = edgemin // (10**6)
        used[v] = True
        for e in edge[v]:
            if not used[e[0]]:
                heappush(edgelst, e[0]+(e[1]+d[v])*(10**6))
    return d

n, m, s, t = map(int, input().split())
Yen = [[] for _ in range(n)]
Snk = [[] 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((v, a))
    Yen[v].append((u, a))
    Snk[u].append((v, b))
    Snk[v].append((u, b))

cos1 = Dijkstra_heap(s-1, Yen)
cos2 = Dijkstra_heap(t-1, Snk)

ans = 0
ANS = []
ANS_append = ANS.append
for yen,snk in zip(cos1[::-1], cos2[::-1]):
  tmp = 10**15-(yen+snk)
  ans = max(ans, tmp)
  ANS_append(ans)
print(*ANS[::-1], sep='\n')

Solution (Python):

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)




from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**17
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans

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

Solution (Python):

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)




from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**16
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans

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

Solution (Python):

import heapq
n, m, s, t = map(int, input().split())
money = 10**15 
graph = [[] for _ in range(n)]

for _ in range(m):
  u, v, a, b = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, a, b]]
  graph[v] += [[u, a, b]]

def dijkstra(s, y):
  dist = [float('inf')]*n 
  dist[s] = 0
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    cost, u = heapq.heappop(q)
    for v, yen, snuuk in graph[u]:
      if y:
        if dist[u] + yen < dist[v]:
          dist[v] = dist[u] + yen 
          heapq.heappush(q, [dist[v], v])
      else:
        if dist[u] + snuuk < dist[v]:
          dist[v] = dist[u] + snuuk 
          heapq.heappush(q, [dist[v], v])
  return dist

y_result = dijkstra(s-1, True)
s_result = dijkstra(t-1, False)

result = [y_result[i]+s_result[i] for i in range(n)]

for i in range(n-1, 0, -1):
  result[i-1] = min(result[i], result[i-1])

for i in range(n):
  print(money-result[i])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, s, t = list(map(int, input().split()))
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = list(map(int, input().split()))
    
    graph[u].append(({'yen': a, 'sunuke': b}, v))
    graph[v].append(({'yen': a, 'sunuke': b}, u))

import heapq

def dijkstra(graph, queue, dist, cost_type):
    while queue:
        d, n = heapq.heappop(queue)
        if dist[n] != -1 and dist[n] < d:
            continue
        for cost, next_n in graph[n]:
            cost_with_type = cost[cost_type]
            if dist[next_n] > d + cost_with_type:
                dist[next_n] = d + cost_with_type
                heapq.heappush(queue, (dist[next_n], next_n))

queue = [(0, s)]
dist_yen = [10 ** 16] + [10 ** 16] * n
dist_yen[s] = 0
dijkstra(graph, queue, dist_yen, 'yen')

queue = [(0, t)]
dist_sunuke = [10 ** 16] + [10 ** 16] * n
dist_sunuke[t] = 0
dijkstra(graph, queue, dist_sunuke, 'sunuke')


answer = [0] + [0] * n
for i in range(n, 0, -1):
    answer[i - 1] = max(answer[i], 10 ** 15 - (dist_yen[i] + dist_sunuke[i]))
for i in range(n):
    print(answer[i])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, s, t = list(map(int, input().split()))
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = list(map(int, input().split()))
    
    graph[u].append(({'yen': a, 'sunuke': b}, v))
    graph[v].append(({'yen': a, 'sunuke': b}, u))

import heapq

def dijkstra(graph, queue, dist, cost_type):
    while queue:
        d, n = heapq.heappop(queue)
        if dist[n] != -1 and dist[n] < d:
            continue
        for cost, next_n in graph[n]:
            cost_with_type = cost[cost_type]
            if dist[next_n] > d + cost_with_type:
                dist[next_n] = d + cost_with_type
                heapq.heappush(queue, (dist[next_n], next_n))

queue = [(0, s)]
dist_yen = [10 ** 16] + [10 ** 16] * n
dist_yen[s] = 0
dijkstra(graph, queue, dist_yen, 'yen')

queue = [(0, t)]
dist_sunuke = [10 ** 16] + [10 ** 16] * n
dist_sunuke[t] = 0
dijkstra(graph, queue, dist_sunuke, 'sunuke')


answer = [0] + [0] * n
for i in range(n, 0, -1):
    answer[i - 1] = max(answer[i], 10 ** 15 - (dist_yen[i] + dist_sunuke[i]))
for i in range(n):
    print(answer[i])