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):
n,m,s,t=map(int,input().split())

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

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


import numpy as np
INF=10**20

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

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


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

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

Solution (Python):
import heapq
inf = float('inf')
def dijkstra(s, n, G):
    dist = [inf]*n
    edges = []
    dist[s] = 0
    for e in G[s]:
        heapq.heappush(edges, e)
    while edges:
        cost, v = heapq.heappop(edges)
        if dist[v] != inf:
            continue
        dist[v] = cost
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv))
    return dist

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

Solution (Python):
import heapq,collections
class Dijkstra():
    def __init__(self):
        self.e=collections.defaultdict(list)
    def add(self,u,v,d):
        self.e[u].append((v,d))
        self.e[v].append((u,d))
    def search(self,s):
        dist = [-1 for _ in range(n)]
        next_point = []
        heapq.heappush(next_point,(0,s))
        while next_point:
            cost,node = heapq.heappop(next_point)
            if dist[node] == -1:
                dist[node] = cost
                for u,d in self.e[node]:
                    if dist[u] == -1:
                        heapq.heappush(next_point,(cost+d,u))
        return dist

n,m,s,t = map(int,input().split())
graph_y = Dijkstra()
graph_s = Dijkstra()
for _ in range(m):
    u,v,a,b = map(int,input().split())
    graph_y.add(u-1,v-1,a)
    graph_s.add(u-1,v-1,b)
dist_y = graph_y.search(s-1)
dist_s = graph_s.search(t-1)
r = [0]*n
for i in range(n):
    r[-i-1] = max(r[-i],10**15-dist_y[-i-1]-dist_s[-i-1])
print(*r,sep='\n')

Solution (Python):
n,m,s,t = map(int,input().split())
import collections
edge = collections.defaultdict(list)
for _ in range(m):
    u,v,a,b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])
yen_dist = [-1 for _ in range(n)]
sunuk_dist = [-1 for _ in range(n)]

import heapq
next_point = []
heapq.heappush(next_point,(0,s-1))
while next_point:
    cost,node = heapq.heappop(next_point)
    if yen_dist[node] == -1:
        yen_dist[node] = cost
        for u,a,_ in edge[node]:
            if yen_dist[u] == -1:
                heapq.heappush(next_point,(cost+a,u))

heapq.heappush(next_point,(0,t-1))
while next_point:
    cost,node = heapq.heappop(next_point)
    if sunuk_dist[node] == -1:
        sunuk_dist[node] = cost
        for u,_,b in edge[node]:
            if sunuk_dist[u] == -1:
                heapq.heappush(next_point,(cost+b,u))

r = [0]*n
for i in range(n):
    r[-i-1] = max(r[-i],10**15-yen_dist[-i-1]-sunuk_dist[-i-1])
print(*r,sep='\n')

Solution (Python):



import collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e=collections.defaultdict(list)
    def add(self,u,v,d,directed=False):
        
        
        
        if directed is False:
            self.e[u].append([v,d])
            self.e[v].append([u,d])
        else:
            self.e[u].append([v,d])
    def delete(self,u,v):
        self.e[u]=[_ for _ in self.e[u] if _[0]!=v]
        self.e[v]=[_ for _ in self.e[v] if _[0]!=u]
    def search(self,s):
        
        
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))
        return d


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

graph1=Dijkstra()
graph2=Dijkstra()
for u,v,a,b in l:
    graph1.add(u,v,a)
    graph2.add(u,v,b)

result_a=graph1.search(s) 
result_b=graph2.search(t) 
ans_list=[float('inf')]   

for i in range(n,0,-1):
    cur=result_a[i]+result_b[i]
    if cur>ans_list[-1]:
        cur=ans_list[-1]
    ans_list.append(cur)


for i in range(len(ans_list[1:])):
    print(10**15-ans_list[-(i+1)])

Solution (Python):
n,m,s,t=map(int,input().split())
uvab=[map(int,input().split()) for i in range(m)]
inf=10**20
c1=[[] for i in range(n)]
c2=[[] for i in range(n)]
for u,v,a,b in uvab:
    c1[u-1].append((v-1,a))
    c1[v-1].append((u-1,a))
    c2[u-1].append((v-1,b))
    c2[v-1].append((u-1,b))
from heapq import heappop,heappush
def dij(c,N,start):
    d=[inf]*N
    d[start]=0
    prev=[-1]*N
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v,w in c[u]:
            if w<inf:
                temp=d[u]+w
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    return d
d1=dij(c1,n,s-1)
d2=dij(c2,n,t-1)
r=[0]*n
for i in range(n):
    r[-i-1]=max(r[-i],10**15-int(d1[-i-1])-int(d2[-i-1]))
print(*r,sep='\n')

Solution (Python):
import heapq

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

cost = [[] for _ in range(n)]
for i in range(m):
    cost[L[i][0]-1].append((L[i][2], L[i][3], L[i][1]-1))
    cost[L[i][1]-1].append((L[i][2], L[i][3], L[i][0]-1))
    
def dijkstra(s, n, cost, c):
    g = 10**6
    d = [10**15]*n
    used = [0]*n
    d[s] = 0
    used[s] = 1
    edgelist = []
    for e in cost[s]:
        heapq.heappush(edgelist, e[c]*g+e[2])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge%g] == 1:
            continue
        v = minedge%g
        d[v] = minedge//g
        used[v] = 1
        for e in cost[v]:
            if used[e[2]] == 0:
                heapq.heappush(edgelist, (e[c]+d[v])*g + e[2])
    return d

jpy = dijkstra(s-1, n, cost, 0)
snuuk = dijkstra(t-1, n, cost, 1)
ans_list = [0]*n
ans_list[n-1] = jpy[n-1]+snuuk[n-1]
for i in range(n-2, -1, -1):
    ans_list[i] = min(ans_list[i+1], jpy[i]+snuuk[i])
    
for i in range(n):
    print(10**15-ans_list[i])

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ高速化版(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    
    res = [INF] * N
    
    que = [src]
    res[src] = 0
    
    while len(que) != 0:
        
        cur = heappop(que)
        
        dist = cur // N
        cur %= N
        
        for nxt, cost in nodes[cur]:
            
            if dist + cost < res[nxt]:
                res[nxt] = dist + cost
                
                heappush(que, (dist+cost)*N+nxt)
    
    return res

N, M, s, t = MAP()
s -= 1
t -= 1
nodes1 = tuple([] for i in range(N))
nodes2 = tuple([] for i in range(N))
for i in range(M):
    u, v, a, b = MAP()
    u -= 1
    v -= 1
    nodes1[u].append((v, a))
    nodes1[v].append((u, a))
    nodes2[u].append((v, b))
    nodes2[v].append((u, b))

res1 = dijkstra(N, nodes1, s)
res2 = dijkstra(N, nodes2, t)

A = [0] * N
for i in range(N):
    
    A[i] = res1[i] + res2[i]


ans = list(accumulate(A[::-1], min))[::-1]
total = 10 ** 15
[print(total-a) for a in ans]

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import *

N, M, S, T = map(int, input().split())
INF = 10 ** 15
graph = [[] for _ in range(N+1)] 

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

def dijkstra(start, mode):
    dist = [INF] * (N+1) 
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, p = heappop(que)
        
        if dist[p] < d:
            continue
        for next_city, *fee in graph[p]:
            d1 = d + fee[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    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(answer.astype(str)))

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

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

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

for _ in range(M):
    u, v, a, b = map(int,input().split())
    
    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
    que = [(0,start)]
    while que:
        
        d, v = heappop(que)
        
        if dist[v] < d:
            continue
        for next_city, *fee in graph[v]:
            
            d1 = d + fee[mode]
            
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    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(answer.astype(str)))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

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

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

for _ in range(M):
    u, v, a, b = map(int,input().split())
    
    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
    que = [(0,start)]
    while que:
        
        d, v = heappop(que)
        
        if dist[v] < d:
            continue
        for w, *a in graph[v]:
            
            d1 = d + a[mode]
            
            if dist[w] > d1:
                dist[w] = d1
                heappush(que, (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(answer.astype(str)))

Solution (Python):
from heapq import heappush, heappop
 
 
class Dijk:
    def __init__(self, n):
        self.table = [[] for i in range(n+1)]
        self.n = n+1
 
    def add(self, x, y, f):
        self.table[x].append((y, f))
 
    def di(self, s):
        inf = float('inf')
        self.val = [inf] * self.n
        self.val[s] = 0
        h = []
        heappush(h, (0, s))
        while h:
            q, i = heappop(h)
            if self.val[i] < q:
                continue
            for x, c in self.table[i]:
                if self.val[x] > self.val[i] + c:
                    self.val[x] = self.val[i] + c
                    heappush(h, (self.val[x], x))
 
    def dist(self, s, t):
        return self.val[t]
 
n, m, s, t = map(int, input().split())
en=Dijk(n)
snu=Dijk(n)
for i in range(m):
    a,b,c,d=map(int,input().split())
    en.add(a,b,c)
    en.add(b,a,c)
    snu.add(a,b,d)
    snu.add(b,a,d)
en.di(s)
snu.di(t)

mod=10**15
t=float('inf')
ans=[]
for i in range(n,0,-1):
    t=min(t,en.dist(s,i)+snu.dist(t,i))
    ans.append(mod-t)
for i in ans[::-1]:
    print(i)

Solution (Python):
from heapq import*
def dijkstra(s,e):
  g=10**6
  d=[10**18]*n
  f=[1]*n
  d[s]=f[s]=0
  q=[]
  for a,b in e[s]:heappush(q,a*g+b)
  while q:
    m=heappop(q)
    if f[m%g]<1:continue
    v=m%g
    x=d[v]=m//g
    f[v]=0
    for y,w in e[v]:
      if f[w]:heappush(q,(x+y)*g+w)
  return d
(n,m,s,t),*z=[map(int,t.split())for t in open(0)]
e,f=eval('[[]for _ in"_"*n],'*2)
for u,v,a,b in z:
  u-=1
  v-=1
  e[u]+=(a,v),
  e[v]+=(a,u),
  f[u]+=(b,v),
  f[v]+=(b,u),
a=[]
m=0
for y,s in zip(dijkstra(s-1,e)[::-1],dijkstra(t-1,f)[::-1]):
  m=max(m,10**15-y-s)
  a+=m,
print(*a[::-1])

Solution (Python):
from heapq import*
def dijkstra(n,s,edge):
    g=10**6
    d=[10**18]*n
    used=[True]*n
    d[s]=0
    used[s]=False
    edgelist=[]
    for a,b in edge[s]:heappush(edgelist,a*g+b)
    while edgelist:
        minedge=heappop(edgelist)
        if not used[minedge%g]:continue
        v1=minedge%g
        c1=d[v1]=minedge//g
        used[v1]=False
        for c2,v2 in edge[v1]:
            if used[v2]:heappush(edgelist,(c1+c2)*g+v2)
    return d
def main():
    n,m,s,t,*z=map(int,open(0).read().split())
    e1,e2=[[[]for _ in range(n)]for _ in range(2)]
    for u,v,a,b in zip(*[iter(z)]*4):
        u-=1
        v-=1
        e1[u]+=(a,v),
        e1[v]+=(a,u),
        e2[u]+=(b,v),
        e2[v]+=(b,u),
    c1=dijkstra(n,s-1,e1)
    c2=dijkstra(n,t-1,e2)
    a=[]
    m=0
    for y,s in zip(c1[::-1],c2[::-1]):
        t=10**15-y-s
        if t>m:m=t
        a+=m,
    print(*a[::-1],sep='\n')
main()

Solution (Python):
from heapq import*
def dijkstra(n,s,edge):
    g=10**6
    d=[10**18]*n
    used=[True]*n
    d[s]=0
    used[s]=False
    edgelist=[]
    for a,b in edge[s]:heappush(edgelist,a*g+b)
    while edgelist:
        minedge=heappop(edgelist)
        if not used[minedge%g]:continue
        v1=minedge%g
        c1=d[v1]=minedge//g
        used[v1]=False
        for c2,v2 in edge[v1]:
            if used[v2]:heappush(edgelist,(c1+c2)*g+v2)
    return d
def main():
    n,m,s,t,*z=map(int,open(0).read().split())
    e1,e2=[[[]for _ in range(n)]for _ in range(2)]
    for u,v,a,b in zip(*[iter(z)]*4):
        u-=1
        v-=1
        e1[u]+=(a,v),
        e1[v]+=(a,u),
        e2[u]+=(b,v),
        e2[v]+=(b,u),
    c1=dijkstra(n,s-1,e1)
    c2=dijkstra(n,t-1,e2)
    a=[]
    m=0
    for y,s in zip(c1[::-1],c2[::-1]):
        t=10**15-y-s
        if t>m:m=t
        a+=m,
    print(*a[::-1],sep='\n')
main()

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

global G

def input_graph(M, uvab):
  global G
  for i in range(M):
    u, v, a, b = uvab[i]
    G[u-1] += [[v-1, (a, b)]]
    G[v-1] += [[u-1, (a, b)]]
  
def dijkstra(N, S, flag):
  global G
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  Q = [(0, S)]
  while Q:
    c, v = heappop(Q)
    if dist[v] < c:
      continue
    for t, cost in G[v]:
      yen, snuuk = cost
      if flag:
        if dist[v] + yen < dist[t]:
          dist[t] = dist[v] + yen
          heappush(Q, (dist[t], t))
      else:
        if dist[v] + snuuk < dist[t]:
          dist[t] = dist[v] + snuuk
          heappush(Q, (dist[t], t))
  return dist

def main():
  global G
  N, M, S, T = map(int, input().split())
  S -= 1
  T -= 1
  uvab = [list(map(int, input().split())) for _ in range(M)]
  G = [[] for _ in range(N)]
  input_graph(M, uvab)
  yen_dist = dijkstra(N, S, True)
  snuuk_dist = dijkstra(N, T, False)
  dist = [yen_dist[i]+snuuk_dist[i] for i in range(N)]
  for i in range(N-2, -1, -1):
    dist[i] = min(dist[i+1], dist[i])
  for i in range(N):
    print(10**15-dist[i])

if __name__ == "__main__":
  main()

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

global G

def input_graph(M, uvab):
  global G
  for i in range(M):
    u, v, a, b = uvab[i]
    G[u-1] += [[v-1, (a, b)]]
    G[v-1] += [[u-1, (a, b)]]
  
def dijkstra(N, S, flag):
  global G
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  Q = [(0, S)]
  while Q:
    c, v = heappop(Q)
    if dist[v] < c:
      continue
    for t, cost in G[v]:
      yen, snuuk = cost
      if flag:
        if dist[v] + yen < dist[t]:
          dist[t] = dist[v] + yen
          heappush(Q, (dist[t], t))
      else:
        if dist[v] + snuuk < dist[t]:
          dist[t] = dist[v] + snuuk
          heappush(Q, (dist[t], t))
  return dist

def main():
  global G, dist
  N, M, S, T = map(int, input().split())
  S -= 1
  T -= 1
  uvab = [list(map(int, input().split())) for _ in range(M)]
  G = [[] for _ in range(N)]
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  input_graph(M, uvab)
  yen_dist = dijkstra(N, S, True)
  snuuk_dist = dijkstra(N, T, False)
  
  
  dist = [yen_dist[i]+snuuk_dist[i] for i in range(N)]
  for i in range(N-2, -1, -1):
    dist[i] = min(dist[i+1], dist[i])
  for i in range(N):
    print(10**15-dist[i])

if __name__ == "__main__":
  main()

Solution (Python):
import heapq as h
n,m,s,t = map(int,input().split())
g = [dict() for _ in range(n+1)]
for _  in range(m):
  u,v,a,b = map(int,input().split())
  g[u][v] = (a,b)
  g[v][u] = (a,b)

def dijkstra(s,g,mode):
  dist = [10**15]*(n+1)
  seen = [False]*(n+1)
  dist[s] = 0
  q = [(0,s)]
  while q:
    d,v = h.heappop(q)
    if seen[v]:
      continue
    seen[v] = True
    dist[v] = d
    for x in g[v]:
      if not seen[x]:
        h.heappush(q,(dist[v]+g[v][x][mode],x))
  return dist

ou = dijkstra(s,g,0)
fuku = dijkstra(t,g,1)
rot = [(ou[i] + fuku[i],i) for i in range(n+1)]
h.heapify(rot)
for i in range(1,n+1):
  if rot[0][1] < i:
    while rot[0][1] < i:
      h.heappop(rot)
  print(10**15 - rot[0][0])

Solution (Python):
import heapq as h
n,m,s,t = map(int,input().split())
g = [dict() for _ in range(n+1)]
for _  in range(m):
  u,v,a,b = map(int,input().split())
  g[u][v] = (a,b)
  g[v][u] = (a,b)

def dijkstra(s,g,mode):
  dist = [10**15]*(n+1)
  seen = [False]*(n+1)
  dist[s] = 0
  q = [(0,s)]
  while q:
    d,v = h.heappop(q)
    if seen[v]:
      continue
    seen[v] = True
    dist[v] = d
    for x in g[v]:
      if not seen[x]:
        h.heappush(q,(dist[v]+g[v][x][mode],x))
  return dist

ou = dijkstra(s,g,0)
fuku = dijkstra(t,g,1)
rot = [(ou[i] + fuku[i],i) for i in range(n+1)]
h.heapify(rot)
for i in range(1,n+1):
  if rot[0][1] < i:
    while rot[0][1] < i:
      h.heappop(rot)
  print(10**15 - rot[0][0])

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

ad1 = [[] for _ in range(n)]

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

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



def dijkstra(start,ad):
    
    N = len(ad)
    dist = [inf] * N
    dist[start] = 0
    
    
    pq = [(dist[start], start)]
    while pq:
        dist_v, v = heappop(pq)
        for nv, nw in ad[v]:
            if dist[nv] > dist_v + nw:
                dist[nv] = dist_v + nw
                heappush(pq,(dist[nv], nv))
            
                
                
    return dist

dist1 = dijkstra(s, ad1)
dist2 = dijkstra(t, ad2)

ans_list = [inf]

for i in range(n)[::-1]:
    ans = min(ans_list[-1], dist1[i] + dist2[i])
    ans_list.append(ans)

ans_list.pop(0)
for ans in ans_list[::-1]:
    print(10**15-ans)

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, e, s, t = MAP()
s-= 1
t-= 1    
G1 = [[]for i in range(n)]
G2 = [[]for i in range(n)]       

for i in range(e):
    fr, to, w1, w2 = MAP()
    G1[fr-1].append((w1, to -1))
    G1[to-1].append((w1, fr -1))
    G2[fr-1].append((w2, to -1))
    G2[to-1].append((w2, fr -1))


def djkstra(s,G):
    visited = [False]*n     
    d = [INF]*n
    que = []
    heapq.heapify(que)
    heapq.heappush(que, (0,s))

    while(len(que)>0):
        vs = heapq.heappop(que)
        distance = vs[0]
        vertex = vs[1]
        if visited[vertex]:
            continue
        d[vertex] = distance
        visited[vertex] = True
        for Gs in G[vertex]:
            if d[Gs[1]] <= distance+Gs[0]:
                continue
            heapq.heappush(que,(distance+Gs[0], Gs[1]))
    
    return d

d_yen = djkstra(s,G1)
d_snuuk = djkstra(t,G2)

d_sum = [0]*n

for i in range(n):
    d_sum[i] = d_yen[i] + d_snuuk[i]

d_sum.reverse()
d_ans = [0]*n
d_ans[0] = d_sum[0]
for i in range(1,n):
    d_ans[i] = min(d_ans[i-1],d_sum[i])

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

Solution (Python):
import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c
    return costs

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

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]

Solution (Python):
import heapq
n, m, s, t = map(int, input().split())
E = [[] for _ in range(n)]
A = [0] * m
B = [0] * m
for i in range(m):
  u, v, a, b = map(int, input().split())
  E[u - 1].append([v - 1, i])
  E[v - 1].append([u - 1, i])
  A[i] = a
  B[i] = b
L = [0] * n
Y = [10 ** 15] * n
S = [10 ** 15] * n
def dijkstra(s, D, W):
  Q = [[0, s]]
  D[s] = 0
  pos = 0
  while Q:
    d, q = heapq.heappop(Q)
    for adj, e in E[q]:
      if d + W[e] < D[adj]:
        D[adj] = d + W[e]
        pos += 1
        heapq.heappush(Q, [D[adj], adj])
  return D
dijkstra(s - 1, Y, A)
dijkstra(t - 1, S, B)
for i in range(n):
  L[i] = Y[i] + S[i]
for i in range(n - 2, -1, -1):
  L[i] = min(L[i + 1], L[i])
for i in range(n):
  print(10 ** 15 - L[i])

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

import heapq
class Heapq:
    def __init__(self, que=[], asc=True):
        if not asc:
            que = [-a for a in que]
        self.__que = que
        heapq.heapify(self.__que)
        self.__sign = 1 if asc else -1

    def pop(self):
        return heapq.heappop(self.__que) * self.__sign

    def push(self, value):
        heapq.heappush(self.__que, value * self.__sign)

    def pushpop(self, value):
        return heapq.heappushpop(self.__que, value * self.__sign) * self.__sign

    def top(self):
        return self.__que[0] * self.__sign

    def size(self):
        return len(self.__que)

def sol():
    N, M, start, end = map(int, input().split())
    start -= 1
    end -= 1
    edgeA = [[] for _ in range(N)]
    edgeB = [[] for _ in range(N)]

    for _ in range(M):
        fr, to, a, b = map(int, input().split())
        fr -= 1
        to -= 1
        edgeA[fr].append((to, a))
        edgeA[to].append((fr, a))
        edgeB[fr].append((to, b))
        edgeB[to].append((fr, b))

    minDistA = [float('inf')] * N
    minDistB = [float('inf')] * N

    que = Heapq([])
    que.push((0, start))

    while que.size():
        dist, now = que.pop()

        if minDistA[now] <= dist:
            continue

        minDistA[now] = dist

        for to, cost in edgeA[now]:
            if minDistA[to] > dist + cost:
                que.push((cost + dist, to))

    que = Heapq([])
    que.push((0, end))

    while que.size():
        dist, now = que.pop()

        if minDistB[now] <= dist:
            continue

        minDistB[now] = dist

        for to, cost in edgeB[now]:
            if minDistB[to] > dist + cost:
                que.push((cost + dist, to))

    ans = [float('inf')] * (N + 1)
    for day in range(N)[:: -1]:
        newDist = minDistA[day] + minDistB[day]
        ans[day] = min(ans[day + 1], newDist)

    offset = 10**15
    for a in ans[: N]:
        print(offset - a)

sol()

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop


def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF] * n
    visited = [False] * n

    dist[start] = 0
    que = [(0, start)]

    while que:
        cost, cur = heappop(que)

        if visited[cur]:
            continue

        visited[cur] = True

        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))

    return dist

n, m, s, t = li()
s -= 1
t -= 1

yen_graph = [[] for _ in range(n)]
snk_graph = [[] for _ in range(n)]

for _ in range(m):
    u, v, a, b = li()
    u -= 1
    v -= 1

    yen_graph[u].append((v, a))
    yen_graph[v].append((u, a))
    snk_graph[u].append((v, b))
    snk_graph[v].append((u, b))

yen_dist = dijkstra(yen_graph, s)
snk_dist = dijkstra(snk_graph, t)

initial = 10**15

ans = [-1]*n
for i in range(n-1, -1, -1):
    if i == n-1:
        ans[i] = initial - (yen_dist[i] + snk_dist[i])

    else:
        ans[i] = max(ans[i+1], initial - (yen_dist[i] + snk_dist[i]))

for ansi in ans:
    print(ansi)

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

def djkstra(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

n, m, s, t = [ int(v) for v in input().split() ]
connect_list = [ [] for i in range(n) ]

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


yen_list = djkstra(s-1,connect_list,n,1)
snuke_list = djkstra(t-1,connect_list,n,2)

remain_snule_list = [ 10**15 - yen_list[i] - snuke_list[i] for i in range(n) ][::-1]


for i in range(n-1):
    if remain_snule_list[i+1] < remain_snule_list[i]:
        remain_snule_list[i+1] = remain_snule_list[i]

remain_snule_list = remain_snule_list[::-1]

for i in remain_snule_list:
    print(i)