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
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union

















from heapq import heapify, heappush, heappop 


from itertools import count, cycle, repeat   










def main():
    Num = Union[int, float]
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    

    class PQueueMin:
        '''
        min priority queue
        Attributes:
            self.pq (list): (priority, count, task) というタプルのエントリからなるヒープ。
            self.counter (iter): ユニークな番号。上記エントリを比較する際、task までに必ず順序関係が決定するようにするためのもの。(task に順序関係がないことがある)
        '''    
        def __init__(self):
            self.pq = []
            self.counter = count()

        def empty(self) -> bool:
            return len(self.pq) == 0

        def add_task(self, task: Any, priority: Num) -> None:
            count = next(self.counter)
            entry = (priority, count, task)
            heappush(self.pq, entry)
        
        def pop_task(self) -> Any:
            if self.empty():
                raise KeyError(f'PQueueMin.pop_task(): pqueue is empty.')
            priority, _, task = heappop(self.pq)
            return (task, priority)

        
    def dijkstra(adj_with_weight: Sequence[Sequence[int]], start: int=0) -> List[Num]:
        '''
        重みつき隣接リストを用いた Dijkstra 法 O((E+V)lgV) (頂点を回るときに最小のものを取り出していくのに VlgV, cost の更新で ElgV)
        負辺を含まぬ重みつきグラフについて、ある頂点から他の頂点までの最短コストを貪欲に計算する
        '''
        V = len(adj_with_weight)
        cost = [float('inf')] * V    
        cost[start] = 0
        fixed = [False] * V
        pq = PQueueMin()
        
        pq.add_task(start, cost[start])
        while not pq.empty():
            
            u, cost_of_u = pq.pop_task()
            if not fixed[u]:
                fixed[u] = True
                for v, weight_of_uv in adj_with_weight[u]:
                    if not fixed[v] and cost[v] > cost_of_u + weight_of_uv:
                        cost[v] = cost_of_u + weight_of_uv
                        pq.add_task(v, cost[v])
        return cost
    

    n, m, s, t = mi()
    s -= 1
    t -= 1    
    adj_yen = [[] for _ in range(n)]
    adj_snuke = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = mi()
        u -= 1
        v -= 1
        adj_yen[u].append((v, a))
        adj_yen[v].append((u, a))
        adj_snuke[u].append((v, b))
        adj_snuke[v].append((u, b))

    mincost_from_s_yen = dijkstra(adj_yen, start=s)
    mincost_from_t_snuke = dijkstra(adj_snuke, start=t)

    
    

    rev_ans = []
    money = 10 ** 15
    prev = inf
    for i in range(n-1, -1, -1):
        
        cost = mincost_from_s_yen[i] + mincost_from_t_snuke[i]
        prev = min(cost, prev)
        rev_ans.append(money - prev)
    
    for elm in reversed(rev_ans):
        print(elm)



if __name__ == "__main__":
    main()

Solution (Python):
import heapq
N, M, S, T = map(int, input().split())
S,T = S-1, T-1 
A = [[] for _ in range(N)]
B = [[] for _ in range(N)]
inf = 10**18

for i in range(M):
  u,v,a,b = map(int, input().split())
  u,v = u-1, v-1
  A[u].append((v,a))
  A[v].append((u,a))
  B[u].append((v,b))
  B[v].append((u,b))
  
def dij(D, parent):
  fixed = [ False for _ in range(N)]
  ret = [ 10**18 for _ in range(N)]
  h = []
  heapq.heappush(h, (0,parent))
  while h:
    d, now = heapq.heappop(h)
    if fixed[now]:
      continue
    fixed[now] = True
    ret[now] = d
    for nxt, cost in D[now]:
      if fixed[nxt]:
        continue
      heapq.heappush(h, (d+cost, nxt))
  return ret
  
DA = dij(A, S)
DB = dij(B, T)

ANS = [ 0 for _ in range(N+1) ]
ANS[N] = inf
for i in range(N-1,-1,-1):
  ANS[i] = min(ANS[i+1], DA[i] + DB[i])
  
for i in range(N):
  print(10**15 - ANS[i])



"""
aのネットワークと、bのネットワーク別々に作って、SからTの最短距離を出す
n-1年目から1年目に遡っていく形で最短を出していく。
A[S][T] と A[S][N-1] + B[N-1][T]を比較すれば良い
"""

Solution (Python):
import heapq
N, M, S, T = map(int, input().split())
S,T = S-1, T-1 
A = [[] for _ in range(N)]
B = [[] for _ in range(N)]
inf = 10**18

for i in range(M):
  u,v,a,b = map(int, input().split())
  u,v = u-1, v-1
  A[u].append((v,a))
  A[v].append((u,a))
  B[u].append((v,b))
  B[v].append((u,b))
  
def dij(D, parent):
  fixed = [ False for _ in range(N)]
  ret = [ 10**18 for _ in range(N)]
  h = []
  heapq.heappush(h, (0,parent))
  while h:
    d, now = heapq.heappop(h)
    if fixed[now]:
      continue
    fixed[now] = True
    ret[now] = d
    for nxt, cost in D[now]:
      if fixed[nxt]:
        continue
      heapq.heappush(h, (d+cost, nxt))
  return ret
  
DA = dij(A, S)
DB = dij(B, T)

ANS = [ 0 for _ in range(N+1) ]
ANS[N] = inf
for i in range(N-1,-1,-1):
  ANS[i] = min(ANS[i+1], DA[i] + DB[i])
  
for i in range(N):
  print(10**15 - ANS[i])



"""
aのネットワークと、bのネットワーク別々に作って、SからTの最短距離を出す
n-1年目から1年目に遡っていく形で最短を出していく。
A[S][T] と A[S][N-1] + B[N-1][T]を比較すれば良い
"""

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










N,M,S,T = map(int,readline().split())
G = [[] for i in range(N)]
for i in range(M):
  u,v,a,b = map(int,readline().split())
  G[u - 1].append((v - 1, a, b))
  G[v - 1].append((u - 1, a, b))

INF = 10 ** 15

import heapq as hq


def get_min_cost(G, label, start):
  dist_from_start = [INF] * len(G)
  
  q = [(0, start, -1)]
  hq.heapify(q)
  while q:
    cost, v, parent = hq.heappop(q)
    if dist_from_start[v] <= cost:
      continue
    dist_from_start[v] = cost
    for child in G[v]:
      if child[0] == parent:
        continue
      hq.heappush(q, (dist_from_start[v] + child[label], child[0], v))
  return dist_from_start
  
dist_from_s = get_min_cost(G, 1, S - 1)
dist_from_g = get_min_cost(G, 2, T - 1)

best = INF
ans = [0] * N
wallet = 10 ** 15
for i in range(N - 1, -1, -1):
  
  if dist_from_s[i] + dist_from_g[i] < best:
    best = dist_from_s[i] + dist_from_g[i]
  ans[i] = wallet - best

for a in ans:
  print(a)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m,s,t = list(map(int, input().split()))
s -= 1
t -= 1
from collections import defaultdict
ns1 = defaultdict(set)
ns2 = defaultdict(set)
for i in range(m):
    u,v,a,b = list(map(int, input().split()))
    u -= 1
    v -= 1
    ns1[u].add((a,v))
    ns1[v].add((a,u))
    ns2[u].add((b,v))
    ns2[v].add((b,u))

def dijkstra(ns, start):
    import heapq
    vals = [None] * n
    h = [(0, start)] 
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
d1 = dijkstra(ns1, s)
d2 = dijkstra(ns2, t)
ds = [None]*n
for i in range(n):
    ds[i] = d1[i] + d2[i]
for i in range(n-2, -1, -1):
    ds[i] = min(ds[i], ds[i+1])
base = pow(10,15)
write("\n".join(map(lambda x: str(base-x), ds)))

Solution (Python):
n,m,s,t=map(int,input().split())
s,t=s-1,t-1
g=[[] for _ in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u,v=u-1,v-1
  g[u].append([v,a,b])
  g[v].append([u,a,b])
inf=float('inf')
froms=[inf]*n
froms[s]=0
fromt=[inf]*n
fromt[t]=0
from heapq import heappop,heappush
ka=set(())
todo=[[0,s]]
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  ka.add(v)
  for nv,nd,_ in g[v]:
    if froms[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      froms[nv]=d+nd
ka=set(())
todo=[[0,t]]
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  ka.add(v)
  for nv,_,nd in g[v]:
    if fromt[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      fromt[nv]=d+nd
pay=[[i,froms[i]+fromt[i]] for i in range(n)]
pay.sort(key=lambda x:x[1],reverse=True)
for i in range(n):
  while pay[-1][0]<i:
    pay.pop()
  print(pow(10,15)-pay[-1][1])

Solution (Python):
import heapq
n, m, s, t = map(int, input().split())
node = [False] * n 
gyen = [[] for i in range(n)]
gsnu = [[] for i in range(n)]

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

distyen = [float('inf')] * n
distsnu = [float('inf')] * n


distyen[s-1] = 0
node[s-1] = True
q = []
for e in gyen[s-1]:
    heapq.heappush(q, e)

while q:
    cost, v = heapq.heappop(q)
    if node[v]:
        continue
    node[v] = True
    distyen[v] = cost
    for e in gyen[v]:
        nextcost, to = e
        heapq.heappush(q, (cost+nextcost, to))

node = [False] * n
distsnu[t-1] = 0
node[t-1] = True
q = []
for e in gsnu[t-1]:
    heapq.heappush(q, e)
while q:
    cost, v = heapq.heappop(q)
    if node[v]:
        continue
    distsnu[v] = cost
    node[v] = True
    for e in gsnu[v]:
        nextcost, to = e
        heapq.heappush(q, (cost+nextcost, to))

ans = []
for i in range(n-1, -1, -1):
    if i == n-1:
        ans.append(pow(10, 15) - distyen[i] - distsnu[i])
    else:
        ans.append(max(ans[-1], pow(10, 15) - distyen[i] - distsnu[i]))
for i in ans[::-1]:
    print(i)

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

from heapq import heappop, heappush
inf = 10 ** 15
cost_a = [inf] * n
cost_a[s] = 0
que = [(cost_a[s], s)]
while que:
    cost, cur = heappop(que)
    if cost > cost_a[cur]:
        continue
    for to, a, _ in edges[cur]:
        if cost_a[to] > cost + a:
            cost_a[to] = cost + a
            heappush(que, (cost_a[to], to))

cost_b = [inf] * n
cost_b[t] = 0
que = [(cost_b[t], t)]
while que:
    cost, cur = heappop(que)
    if cost > cost_b[cur]:
        continue
    for to, _, b in edges[cur]:
        if cost_b[to] > cost + b:
            cost_b[to] = cost + b
            heappush(que, (cost_b[to], to))

ans = [10 ** 15]
for i in range(n-1, -1, -1):
    ans.append(min(ans[-1], cost_a[i] + cost_b[i]))
for i in range(1, n+1):
    print(10 ** 15 - ans[-i])

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

import heapq

def dijkstra(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())
s,t=s-1,t-1
edge1=[[] for _ in range(n)]
edge2=[[] for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  edge1[u-1].append([a,v-1])
  edge1[v-1].append([a,u-1])
  edge2[u-1].append([b,v-1])
  edge2[v-1].append([b,u-1])
d1=dijkstra(s,edge1)
d2=dijkstra(t,edge2)
INF=10**15
ans=[INF]*n
ans[n-1]=int(d1[n-1]+d2[n-1])
for i in range(n-2,-1,-1):
  tmp=int(d1[i]+d2[i])
  ans[i]=min(tmp,ans[i+1])
for i in range(n):
  print(INF-ans[i])

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():


    
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        


        class Edge():
            

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            
            self.inf=10**16
            self.G = [[] for _ in range(V)] 
            self. _E = 0 
            self._V = V 

        
        def E(self):
            return self._E

        
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):
            
            que = [] 
            d = [self.inf] * self.V()

            
            

            d[s] = 0
            heapq.heappush(que,(0,s)) 

            while len(que)!=0:
                
                cost,v = heapq.heappop(que)

                
                if d[v] < cost:
                    continue

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

                        
                        

                        heapq.heappush(que,(d[e.to],e.to)) 

            """
            path = []
            pos = g 
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                
                pos = prev[pos]
            path.reverse()
            

            return d
    
    
    N,M,s,t=MI()
    s-=1
    t-=1
    djk=Dijkstra(N)
    djk2=Dijkstra(N)
    
    for _ in range(M):
        u,v,a,b,=MI()
        u-=1
        v-=1
        djk.add2(u,v,a)
        djk2.add2(u,v,b)
        
    
    Ds=djk.shortest_path(s)
    Dt=djk2.shortest_path(t)
    
    
    cost=[0]*N
    for i in range(N):
        cost[i]=Ds[i]+Dt[i]
        
    mon=10**15
    ans=[0]*N
    temp=0
    for i in range(N-1,-1,-1):
        ans[i]=max(temp,mon-cost[i])
        temp=ans[i]
        
    for i in range(N):
        print(ans[i])
    
    
    

main()

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

import heapq

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

edges = [[] for i in range(N)]
edget = [[] for i in range(N)]

for i in range(M):
    u,v,a,b = map(int,readline().split())
    u -= 1
    v -= 1
    edges[u].append([a,v])
    edges[v].append([a,u])
    edget[u].append([b,v])
    edget[v].append([b,u])

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

ds = dijkstra_heap(S-1,N,edges)
dt = dijkstra_heap(T-1,N,edget)

ans = [INF]*N
ans[0] = ds[N-1] + dt[N-1]
for i in range(1,N):
    ans[i] = min(ans[i-1],ds[N-i-1]+dt[N-i-1])
for i in range(N):
    print(10**15-ans[N-1-i])

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

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


class Dijkstra():
    class Edge():

        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):

        self.G = [[] for i in range(V+1)]
        self._E = 0
        self._V = V

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

    def s_path(self, s):
        """ 始点sから頂点iまでの最短路リスト 
        """
        que = []
        heapq.heapify(que)
        d = [10**15] * (self._V+1)
        d[s] = 0
        heapq.heappush(que, (0, s))
        while que:
            cost, v = heapq.heappop(que)
            if d[v] < cost:
                continue

            for e in self.G[v]:
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d
      
      
graph_snuke = Dijkstra(N)
graph_yen = Dijkstra(N)
for _ in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen.add(u, v, a)
    graph_yen.add(v, u, a)
    graph_snuke.add(u, v, b)
    graph_snuke.add(v, u, b)

yen = graph_yen.s_path(S)
snuke = graph_snuke.s_path(T)
minimum_case = [10**15 for i in range(N+1)]
for i in range(N):
    minimum_case[1+i] -= (yen[i+1]+snuke[i+1])
for i in range(N-1, -1, -1):
    minimum_case[i] = max(minimum_case[i], minimum_case[i+1])
for i in range(1, N+1):
    print(minimum_case[i])

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

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


class Edge():

    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


class Dijkstra():
    def __init__(self, V):

        self.G = [[] for i in range(V+1)]
        self._E = 0
        self._V = V

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

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路リスト 
        """
        que = []
        heapq.heapify(que)
        d = [10**15] * (self._V+1)
        d[s] = 0
        heapq.heappush(que, (0, s))  

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

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


graph_snuke = Dijkstra(N)
graph_yen = Dijkstra(N)
for _ in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen.add(u, v, a)
    graph_yen.add(v, u, a)
    graph_snuke.add(u, v, b)
    graph_snuke.add(v, u, b)

yen = graph_yen.shortest_path(S)
snuke = graph_snuke.shortest_path(T)
minimum_case = [10**15 for i in range(N+1)]
for i in range(N):
    minimum_case[1+i] -= (yen[i+1]+snuke[i+1])
for i in range(N-1, -1, -1):
    minimum_case[i] = max(minimum_case[i], minimum_case[i+1])
for i in range(1, N+1):
    print(minimum_case[i])

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

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

import heapq


class Edge():
    """ 重み付き有向辺 """

    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


class Dijkstra():
    def __init__(self, V):

        self.G = [[] for i in range(V+1)]
        self._E = 0
        self._V = V

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

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路リスト 
        """
        que = []
        heapq.heapify(que)
        d = [float("inf")] * (self._V+1)
        d[s] = 0
        heapq.heappush(que, (0, s))  

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

            for i in range(len(self.G[v])):
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d
graph_snuke = Dijkstra(N)
graph_yen = Dijkstra(N)
for _ in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen.add(u, v, a)
    graph_yen.add(v, u, a)
    graph_snuke.add(u, v, b)
    graph_snuke.add(v, u, b)

yen = graph_yen.shortest_path(S)
snuke = graph_snuke.shortest_path(T)
minimum_case = [10**15 for i in range(N+1)]
for i in range(N):
    minimum_case[1+i] -= (yen[i+1]+snuke[i+1])
for i in range(N-1, -1, -1):
    minimum_case[i] = max(minimum_case[i], minimum_case[i+1])
for i in range(1, N+1):
    print(minimum_case[i])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
from itertools import accumulate
n,m,s,t= map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]

g = defaultdict(list)
c = {}
'''
for i in range(1,n+1):
    g[i].append(n+i)
    c[(i,n+i)] = 0
    '''
for u,v,a,b in uvab:
    g[u].append(v)
    g[v].append(u)
    g[n+u].append(n+v)
    g[n+v].append(n+u)
    c[(u,v)] = a
    c[(v,u)] = a
    c[(n+u,n+v)] = b
    c[(n+v,n+u)] = b

inf = 10**15
ds2t = [inf for i in range(2*n+1)]
ds2t[s] = 0

dq = deque([s])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if ds2t[nv] > ds2t[v] + c[(v,nv)]:
            ds2t[nv] = ds2t[v] + c[(v,nv)]
            dq.append(nv)


dt2s = [inf for i in range(2*n+1)]
dt2s[n+t] = 0

dq = deque([n+t])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if dt2s[nv] > dt2s[v] + c[(v,nv)]:
            dt2s[nv] = dt2s[v] + c[(v,nv)]
            dq.append(nv)

ds = []
for i in range(1,n+1):
    ds.append(ds2t[i] + dt2s[n+i])

ds = accumulate(ds[::-1], min)

for d in reversed(list(ds)): 
    print(10**15-d)

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
from heapq import *

def dijkstra(G, sta):
    dist = [10**18]*n
    dist[sta] = 0
    pq = []
    heappush(pq, (0, sta))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    return dist

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

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

d1 = dijkstra(G1, s-1)
d2 = dijkstra(G2, t-1)
ans = [0]

for i in range(n-1, -1, -1):
    ans.append(max(ans[-1], 10**15-d1[i]-d2[i]))

ans.reverse()

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

Solution (Python):
def f():
    import sys
    input=sys.stdin.buffer.readline
    inputs=sys.stdin.buffer.readlines
    n,m,s,t=map(int,input().split())
    yedge=[[]for i in range(n+1)]
    sedge=[[]for i in range(n+1)]
    for i in inputs():
        fro,to,cy,cs=map(int,i.split())
        yedge[fro].append((to,cy))
        yedge[to].append((fro,cy))
        sedge[fro].append((to,cs))
        sedge[to].append((fro,cs))
    from heapq import  heappop, heappush
    def dijkstra(edges,start):
        
        
        
        d=[-1]*len(edges)
        
        hq=[(0,start)]
        while hq:
            c,v=heappop(hq)
            if d[v]!=-1:continue
            d[v]=c
            
            for to,cos in edges[v]:
                if d[to]==-1:heappush(hq,(c+cos,to))
        return d
    yd=dijkstra(yedge,s)
    sd=dijkstra(sedge,t)
    ret=[]
    ans=0
    k=10**15
    for i in range(n,0,-1):
        ans=max(ans,k-yd[i]-sd[i])
        ret.append(ans)
    ret.reverse()
    print(*ret,sep="\n")
if __name__ == "__main__":
    f()

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

class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        prev = [None for _ in range(self.n)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    prev[adj] = node
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

import sys
input = sys.stdin.readline

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

E1 = []
E2 = []

for _ in range(M):
    u, v, a, b = map(int, input().split())
    E1.append((u, v, a))
    E2.append((u, v, b))
    
g1 = Graph(N, E1)
g2 = Graph(N, E2)
dist_from_s = g1.dijkstra(S - 1)
dist_from_t = g2.dijkstra(T - 1)

res = list()
tmp = 0

for i in range(N)[::-1]:
    tmp = max(tmp, 10**15 - dist_from_t[i] - dist_from_s[i])
    res.append(tmp)
    
print('\n'.join(map(str, res[::-1])))

Solution (Python):
import heapq

def dijkstra(s, edge):
    cost = [float('inf')] * n
    cost[s] = 0
    hq = [(0, s)]
    heapq.heapify(hq)
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]:
            continue
        for d, u in edge[v]:
            if c + d < cost[u]:
                heapq.heappush(hq, (c + d, u))
                cost[u] = c + d
    return cost

n, m, s, t = map(int, input().split())
s -= 1
t -= 1
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    yen[u].append((a, v))
    yen[v].append((a, u))
    snuuk[u].append((b, v))
    snuuk[v].append((b, u))
py = dijkstra(s, yen)
ps = dijkstra(t, snuuk)
res = [-1] * n
tmp = 10 ** 16
for i in range(n-1, -1, -1):
    if py[i] + ps[i] < tmp:
        tmp = py[i] + ps[i]
    res[i] = 10 ** 15 - tmp
print(*res, sep='\n')

Solution (Python):
from heapq import heappush, heappop

INF = float("inf")
def dijkstra(E, r):
    D = [INF] * len(E)
    D[r] = 0

    Q = [(0, r)]
    while Q:
        dist, cur = heappop(Q)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, (cand, nxt))

    return D


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

A = dijkstra(A, S)
B = dijkstra(B, T)

init = 10 ** 15

ans = []
cur = INF
for a, b in zip(reversed(A[1:]), reversed(B[1:])):
    cur = min(cur, a + b)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)