Problem:
 Score : 400 points    Problem Statement Kenkoooo is planning a trip in Republic of Snuke.
In this country, there are n cities and m trains running.
The cities are numbered 1 through n , and the i -th train connects City u_i and v_i bidirectionally.
Any city can be reached from any city by changing trains.  Two currencies are used in the country: yen and snuuk.
Any train fare can be paid by both yen and snuuk.
The fare of the i -th train is a_i yen if paid in yen, and b_i snuuk if paid in snuuk.  In a city with a money exchange office, you can change 1 yen into 1 snuuk.
However, when you do a money exchange, you have to change all your yen into snuuk.
That is, if Kenkoooo does a money exchange when he has X yen, he will then have X snuuk.
Currently, there is a money exchange office in every city, but the office in City i will shut down in i years and can never be used in and after that year.  Kenkoooo is planning to depart City s with 10^{15} yen in his pocket and head for City t , and change his yen into snuuk in some city while traveling.
It is acceptable to do the exchange in City s or City t .  Kenkoooo would like to have as much snuuk as possible when he reaches City t by making the optimal choices for the route to travel and the city to do the exchange.
For each i=0,...,n-1 , find the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i years.
You can assume that the trip finishes within the year.      Constraints  2 \leq n \leq 10^5  1 \leq m \leq 10^5  1 \leq s,t \leq n  s \neq t  1 \leq u_i < v_i \leq n  1 \leq a_i,b_i \leq 10^9  If i\neq j , then u_i \neq u_j or v_i \neq v_j .  Any city can be reached from any city by changing trains.  All values in input are integers.         Input Input is given from Standard Input in the following format:  n  m  s  t  u_1  v_1  a_1  b_1  :  u_m  v_m  a_m  b_m       Output Print n lines.
In the i -th line, print the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i-1 years.        Sample Input 1 4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1      Sample Output 1 999999999999998
999999999999989
999999999999979
999999999999897  After 0 years, it is optimal to do the exchange in City 1 . After 1 years, it is optimal to do the exchange in City 2 . Note that City 1 can still be visited even after the exchange office is closed.
Also note that, if it was allowed to keep 1 yen when do the exchange in City 2 and change the remaining yen into snuuk, we could reach City 3 with 999999999999998 snuuk, but this is NOT allowed. After 2 years, it is optimal to do the exchange in City 3 . After 3 years, it is optimal to do the exchange in City 4 .
Note that the same train can be used multiple times.       Sample Input 2 8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879      Sample Output 2 999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





def dijkstra(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  f = [False] * N
  q = [(0, start)]
  while q:
    c,u = heapq.heappop(q)
    if f[u]: continue
    d[u] = c
    f[u] = True
    for c,v in graph[u]:
      if not f[v]:
        heapq.heappush(q, (c + d[u], v))
  return d

N,M,s,t = IL()
grapha = [[] for i in range(N)]
graphb = [[] for i in range(N)]
for _ in range(M):
  u,v,a,b = IL()
  grapha[u-1].append((a,v-1))
  grapha[v-1].append((a,u-1))
  graphb[u-1].append((b,v-1))
  graphb[v-1].append((b,u-1))
  
da = dijkstra(grapha, s-1)
db = dijkstra(graphb, t-1)

moto = 10**15
ans = [moto-INF]
for i in range(N)[::-1]:
  ans.append(max(ans[-1],moto-da[i]-db[i]))
for i in range(1,N+1)[::-1]:
  print(ans[i])

Solution (Python):
import sys
import heapq

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


def dijkstra(N, s0, edge):

    d = [INF] * N
    used = [False] * N
    edgelist = [(0, s0)]
    heapq.heapify(edgelist)

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d


def main():

    N, M, S, T = in_nn()
    S, T = S - 1, T - 1

    edge_yen = [[] for _ in range(N)]
    edge_sun = [[] for _ in range(N)]

    for i in range(M):
        u, v, a, b = in_nn()
        u, v = u - 1, v - 1
        edge_yen[u].append((a, v))
        edge_yen[v].append((a, u))
        edge_sun[u].append((b, v))
        edge_sun[v].append((b, u))

    d_s_yen = dijkstra(N, S, edge_yen)
    d_t_sun = dijkstra(N, T, edge_sun)

    money = 10**15
    year = [0] * N
    for i in range(N):
        year[i] = money - d_s_yen[i] - d_t_sun[i]

    ans = [0] * N
    year_max = 0
    for i in range(N - 1, -1, -1):
        year_max = max(year_max, year[i])
        ans[i] = year_max

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):
import heapq

N, M, s, t = map(int, input().split())
inf = 10 ** 18

def dijkstra(start, G):
    q = [(0, start)]
    heapq.heapify(q)
    cost = [inf] * N
    cost[start] = 0
    while q:
        c, v = heapq.heappop(q)
        if c > cost[v]:
            continue
        for d, u in G[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(q, (tmp, u))
    return cost


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

s2i = dijkstra(s - 1, Ga)
i2t = dijkstra(t - 1, Gb)

c = [0] * N
tmp = 10 ** 18
for i in range(N):
    tmp = min(tmp, s2i[-(i + 1)] + i2t[-(i + 1)])
    c[-(i + 1)] = tmp

for cc in c:
    print(10 ** 15 - cc)

Solution (Python):
import heapq

N, M, s, t = map(int, input().split())
inf = 10 ** 18

def dijkstra(start, G):
    q = [(0, start)]
    heapq.heapify(q)
    cost = [inf] * N
    cost[start] = 0
    while q:
        c, v = heapq.heappop(q)
        if c > cost[v]:
            continue
        for d, u in G[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(q, (tmp, u))
    return cost


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

s2i = dijkstra(s - 1, Ga)
i2t = dijkstra(t - 1, Gb)

c = [0] * N
tmp = 10 ** 18
for i in range(N):
    tmp = min(tmp, s2i[-(i + 1)] + i2t[-(i + 1)])
    c[-(i + 1)] = tmp

for cc in c:
    print(10 ** 15 - cc)

Solution (Python):

from heapq import heappop, heappush
INF = float('inf')
def dijkstra(s,n,g): 
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

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

de = dijkstra(s,n,ge)
ds = dijkstra(t,n,gs)
c = []
for i in range(n):
  c.append((de[i]+ds[i],i))
c.sort()
j = 0
for i in range(n):
  while(c[j][1] < i):
    j += 1
  print(10**15-c[j][0])

Solution (Python):
from networkx import*
(N,M,*S),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for*u,a,b in t:G.add_edge(*u,y=a,s=b)
b=m=10**15
y,s,*r=map(eval(dir()[761]),(G,G),S,(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

Solution (Python):
from networkx import*
(N,M,*S),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for u,v,a,b in t:G.add_edge(u,v,y=a,s=b)
b=m=10**15
y,s,*r=map(eval(dir()[761]),(G,G),S,(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

Solution (Python):
from networkx import*
(N,M,S,T,*r),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for u,v,a,b in t:G.add_edge(u,v,y=a,s=b)
b=m=10**15
y,s=map(eval(dir()[763]),(G,G),(S,T),(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

Solution (Python):
from networkx import*
(N,M,S,T,*r),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for u,v,a,b in t:G.add_edge(u,v,y=a,s=b)
b=m=10**15
y,s=map(f:=eval(dir()[763]),(G,G),(S,T),(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

Solution (Python):
import sys
from networkx import*
i=sys.stdin.readline
m=10**15
N,M,S,T=map(int,i().split())
G=Graph()
G.add_nodes_from(range(1,N+1))
for _ in range(M):u,v,a,b=map(int,i().split());G.add_edge(u,v,y=a,s=b)
y=single_source_dijkstra_path_length(G,S,weight='y')
s=single_source_dijkstra_path_length(G,T,weight='s')
a=[m]*(N+1)
for j in range(N,0,-1):a[j-1]=min(a[j],y[j]+s[j])
for x in a[:N]:print(m-x)

Solution (Python):
import sys
from networkx import*
i=sys.stdin.readline
m=10**15
N,M,S,T=map(int,i().split())
G=Graph()
G.add_nodes_from(range(1,N+1))
for _ in range(M):
  u,v,a,b=map(int,input().split())
  G.add_edge(u,v,y=a,s=b)
y=single_source_dijkstra_path_length(G,S,weight='y')
s=single_source_dijkstra_path_length(G,T,weight='s')
a=[m]*(N+1)
for j in range(N,0,-1):
  a[j-1]=min(a[j],y[j]+s[j])
for x in a[:N]:
  print(m-x)

Solution (Python):
import sys
import networkx as nx

input = sys.stdin.buffer.readline

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

G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    u, v, a, b = map(int, input().split())
    G.add_edge(u, v, yen=a, snuuk=b)

yen_path = nx.single_source_dijkstra_path_length(G, S, weight='yen')
snuuk_path = nx.single_source_dijkstra_path_length(G, T, weight='snuuk')

ans = [MAX] * (N + 1)
for i in range(N, 0, -1):
    ans[i - 1] = min(ans[i], yen_path[i] + snuuk_path[i])
for x in ans[:N]:
    print(MAX - x)

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




import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[0]*n
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)
check=float("INF")
for i in range(n-1,-1,-1):
  check=min(d_yen[i]+d_sunuke[i],check)
  ans[i]=check


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

Solution (Python):
from heapq import heappush,heappop

def main():
  n,m,s,t=map(int,input().split())
  INF=10**20
  G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
  for i in range(m):
    u,v,a,b=map(int,input().split())
    G1[u-1][v-1] = G1[v-1][u-1] = a
    G2[u-1][v-1] = G2[v-1][u-1] = b

  def dijkstra(G,start = 0):
      d = [INF for i in range(len(G))]
      d[start] = 0
      que = []
      heappush(que, (0, start))

      while len(que):
          p = heappop(que)
          v = p[1]
          if d[v] < p[0]:
              continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, (d[u], u))
      return d

  d1 = dijkstra(G1,s-1)
  d2 = dijkstra(G2,t-1)

  ans=[]
  MIN = INF
  for i in range(n-1,-1,-1):
    MIN = min(MIN,d1[i]+d2[i])
    if i == s-1:
      MIN = min(MIN,d2[s-1])
    if i == t-1:
      MIN = min(MIN,d1[t-1])

    ans.append(MIN)

  for a in reversed(ans):
    print(10**15-a)
  
if __name__=="__main__":
  main()

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

def main():
  n,m,s,t=map(int,input().split())
  INF=10**20
  G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
  for i in range(m):
    u,v,a,b=map(int,input().split())
    G1[u-1][v-1] = G1[v-1][u-1] = a
    G2[u-1][v-1] = G2[v-1][u-1] = b

  def dijkstra(G,start = 0):
      d = [INF for i in range(len(G))]
      d[start] = 0
      que = []
      heappush(que, (0, start))

      while len(que):
          p = heappop(que)
          v = p[1]
          if d[v] < p[0]:
              continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, (d[u], u))
      return d

  d1 = dijkstra(G1,s-1)
  d2 = dijkstra(G2,t-1)

  ans=deque()
  MIN = INF
  for i in range(n-1,-1,-1):
    MIN = min(MIN,d1[i]+d2[i])
    if i == s-1:
      MIN = min(MIN,d2[s-1])
    if i == t-1:
      MIN = min(MIN,d1[t-1])

    ans.appendleft(10**15-MIN)

  print(*ans)
  
if __name__=="__main__":
  main()

Solution (Python):
from heapq import heappush,heappop

def main():
  n,m,s,t=map(int,input().split())
  INF=10**20
  G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
  for i in range(m):
    u,v,a,b=map(int,input().split())
    G1[u-1][v-1] = G1[v-1][u-1] = a
    G2[u-1][v-1] = G2[v-1][u-1] = b

  def dijkstra(G,start = 0):
      d = [INF for i in range(len(G))]
      d[start] = 0
      que = []
      heappush(que, (0, start))

      while len(que):
          p = heappop(que)
          v = p[1]
          if d[v] < p[0]:
              continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, (d[u], u))
      return d

  d1 = dijkstra(G1,s-1)
  d2 = dijkstra(G2,t-1)

  ans=[]
  MIN = INF
  for i in range(n-1,-1,-1):
    MIN = min(MIN,d1[i]+d2[i])
    if i == s-1:
      MIN = min(MIN,d2[s-1])
    if i == t-1:
      MIN = min(MIN,d1[t-1])

    ans.append(MIN)

  print(*[10**15-ans[-i-1] for i in range(n)])
  
if __name__=="__main__":
  main()

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

from heapq import heappush, heappop,heappushpop,heapify
def dks(g,start,num_v):
    INF=float('inf')
    visited = set()
    hq = []
    heappush(hq, (0,start))
    cost = [INF] * num_v
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            heappush(hq, (shortest + t, j))
    return cost

link_yen = [[] for _ in range(n)]
link_snk = [[] for _ in range(n)]
for u,v,a,b in uvab:
    link_yen[u-1].append([v-1,a])
    link_yen[v-1].append([u-1,a])
    link_snk[u-1].append([v-1,b])
    link_snk[v-1].append([u-1,b])

cost_yen = dks(link_yen,s-1,n)
cost_snk = dks(link_snk,t-1,n)

ans=[]
mn=float("inf")
for i in reversed(range(n)):
    new_cost = cost_yen[i] + cost_snk[i]
    mn=min(mn,new_cost)
    ans.append(mn)

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

Solution (Python):
from heapq import heappush,heappop

n,m,s,t=map(int,input().split())
INF=10**20
G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  G1[u-1][v-1] = G1[v-1][u-1] = a
  G2[u-1][v-1] = G2[v-1][u-1] = b
  
def dijkstra(G,start = 0):
    d = [INF for i in range(len(G))]
    d[start] = 0
    que = []
    heappush(que, (0, start))

    while len(que):
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d
  
d1 = dijkstra(G1,s-1)
d2 = dijkstra(G2,t-1)

ans=[]
MIN = INF
for i in range(n-1,-1,-1):
  MIN = min(MIN,d1[i]+d2[i])
  if i == s-1:
    MIN = min(MIN,d2[s-1])
  if i == t-1:
    MIN = min(MIN,d1[t-1])
    
  ans.append(MIN)
  
print(*[10**15-ans[-i-1] for i in range(n)])

Solution (Python):
import sys
input = sys.stdin.readline
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')
costy = [INF] * N
costy[S] = 0
hq = [(0,S)]
while hq:
    c,v = heapq.heappop(hq)
    for to,a,_ in es[v]:
        if costy[to] <= c+a: continue
        costy[to] = c+a
        heapq.heappush(hq, (c+a,to))

costs = [INF] * N
costs[T] = 0
hq = [(0,T)]
while hq:
    c,v = heapq.heappop(hq)
    for to,_,b in es[v]:
        if costs[to] <= c+b: continue
        costs[to] = c+b
        heapq.heappush(hq, (c+b,to))

ans = [0]
for y,s in reversed(list(zip(costy,costs))):
    ans.append(max(ans[-1], 10**15 - y - s))

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

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def dijkstra_heap(v, start, edge):
    """
    ダイクストラ法
    :param v: 走査するグラフの頂点数
    :param start: 始点
    :param edge: 重み付き隣接リスト。[cost, node]の形で渡す
    :return: 始点から各頂点への最短距離
    """
    res = [f_inf] * v
    res[start] = 0
    checked = [False] * v
    checked[start] = True
    edge_list = []
    for u in edge[start]:
        heappush(edge_list, u)
    while len(edge_list):
        min_edge = heappop(edge_list)
        cost, node = min_edge
        if not checked[node]:
            res[node] = cost
            checked[node] = True
            for next_cost, next_node in edge[node]:
                if not checked[next_node]:
                    heappush(edge_list, [next_cost + cost, next_node])
    return res


def resolve():
    init = 10 ** 15
    n, m, s, t = map(int, input().split())
    edge_en = [[] for _ in range(n)]
    edge_sn = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        edge_en[u - 1].append([a, v - 1])
        edge_en[v - 1].append([a, u - 1])
        edge_sn[u - 1].append([b, v - 1])
        edge_sn[v - 1].append([b, u - 1])

    cost_en = dijkstra_heap(n, s - 1, edge_en)
    cost_sn = dijkstra_heap(n, t - 1, edge_sn)
    costs = []
    for i in range(n):
        total_cost = cost_en[i] + cost_sn[i]
        costs.append([total_cost, i])

    heapify(costs)
    cost = 0
    now = -1
    for i in range(n):
        while costs and now < i:
            if costs[0][1] < i:
                heappop(costs)
            else:
                cost, now = heappop(costs)
                break
        print(init - cost)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import defaultdict
import heapq


def dijkstra(N, adj, cost, start):
    INF = 10 ** 15
    min_cost = [INF] * N
    min_cost[start] = 0
    que = [(0, start)]
    while len(que) > 0:
        c, node = heapq.heappop(que)
        for next_node in adj[node]:
            next_cost = min_cost[node] + cost[(node, next_node)]
            if next_cost < min_cost[next_node]:
                min_cost[next_node] = next_cost
                heapq.heappush(que, (next_cost, next_node))
    return min_cost


def main():
    MONEY_MAX = 10 ** 15
    N, M, S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    adj = defaultdict(list)
    yen = defaultdict(int)
    snuuk = defaultdict(int)
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        adj[U].append(V)
        adj[V].append(U)
        yen[(U, V)], yen[(V, U)] = A, A
        snuuk[(U, V)], snuuk[(V, U)] = B, B
    min_yen = dijkstra(N, adj, yen, S)
    min_snuuk = dijkstra(N, adj, snuuk, T)
    
    min_cost = [y + s for y, s in zip(min_yen, min_snuuk)]
    city_cost = [(cost, city) for city, cost in enumerate(min_cost)]
    heapq.heapify(city_cost)
    ans = [0] * N
    cost, city = heapq.heappop(city_cost)
    for i in range(N):
        
        while city < i:
            cost, city = heapq.heappop(city_cost)
        ans[i] = MONEY_MAX - cost
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Solution (Python):
n,m,s,t=map(int,input().split())
yen=[[]*(n+1) for i in range(n+1)]
sunuke=[[]*(n+1) for i in range(n+1)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u].append((a,v))
  yen[v].append((a,u))
  sunuke[u].append((b,v))
  sunuke[v].append((b,u))
  
import heapq

def dijkstra(n,m,s,es):
  
  used=[False]*(n+1)
  d=[float("INF")]*(n+1)
  d[s]=0
  used[s]=True
  q=[]
  for to in es[s]:
    heapq.heappush(q,to)
  while len(q)>0:
    minedge=heapq.heappop(q)
    v=minedge[1]
    if used[v]==True:
      continue
    cost=minedge[0]
    d[v]=cost
    used[v]=True
    for to in es[v]:
      heapq.heappush(q,(d[v]+to[0],to[1]))
  return d


d_yen=dijkstra(n,m,s,yen)
d_sunuke=dijkstra(n,m,t,sunuke)

ans=[float("INF")]*(n+1)
num=float("INF")
for i in range(n,0,-1):
  num=min(d_yen[i]+d_sunuke[i],num)
  ans[i]=num
  
for j in range(1,n+1):
  print(10**15-ans[j])

Solution (Python):
n,m,s,t=map(int,input().split())
yen=[[]*(n+1) for i in range(n+1)]
sunuke=[[]*(n+1) for i in range(n+1)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u].append((a,v))
  yen[v].append((a,u))
  sunuke[u].append((b,v))
  sunuke[v].append((b,u))
  
import heapq

def dijkstra(n,m,s,es):
  
  used=[False]*(n+1)
  d=[float("INF")]*(n+1)
  d[s]=0
  used[s]=True
  q=[]
  for to in es[s]:
    heapq.heappush(q,to)
  while len(q)>0:
    minedge=heapq.heappop(q)
    v=minedge[1]
    if used[v]==True:
      continue
    cost=minedge[0]
    d[v]=cost
    used[v]=True
    for to in es[v]:
      heapq.heappush(q,(d[v]+to[0],to[1]))
  return d


d_yen=dijkstra(n,m,s,yen)
d_sunuke=dijkstra(n,m,t,sunuke)

ans=[float("INF")]*(n+1)
num=float("INF")
for i in range(n,0,-1):
  num=min(d_yen[i]+d_sunuke[i],num)
  ans[i]=num
  
for j in range(1,n+1):
  print(10**15-ans[j])

Solution (Python):
import heapq
def dijkstra(s, n, g): 
    INF = 10**18
    d = [INF] * n
    d[s] = 0
    que = [] 
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue 
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                heapq.heappush(que, (d[next_v], next_v))
    return d


n,m,s,t = map(int, input().split())
gal = [ [] for _ in range(n+1) ]
gbl = [ [] for _ in range(n+1) ]

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

adl = dijkstra(s,n+1,gal)
bdl = dijkstra(t,n+1,gbl)
ansl = [0]*n
curr_min = 10**18


for i in range(n-1,-1,-1):
    cost = adl[i+1] + bdl[i+1]
    curr_min = min(cost, curr_min)
    ansl[i] = 10**15-curr_min
    
    

for ans in ansl:
    print(ans)

Solution (Python):
from heapq import heappush as pu, heappop as po

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

def dik(s,v):
    S = [float("INF")]*(n)
    S[s] = 0
    h = []
    pu(h,[0,s])
    while h:
        d,now = po(h)
        for nex in e[now]:
            a,b = nex[0],nex[v]
            if d+b < S[a]:
                S[a] = d+b
                pu(h,[d+b,a])
    return S[::-1]
ans = []
cost = 10**15
now = 0
for i,j in zip(dik(s-1,1),dik(t-1,2)):
    now = max(now,cost-i-j)
    ans.append(now)
print(*ans[::-1],sep="\n")

Solution (Python):
from heapq import heappush as pu, heappop as po

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))

def dik(s,v):
    S = [float("INF")]*(n+1)
    S[s] = 0
    h = []
    pu(h,[0,s])
    while h:
        d,now = po(h)
        for nex in e[now]:
            a,b = nex[0],nex[v]
            if d+b < S[a]:
                S[a] = d+b
                pu(h,[d+b,a])
    return S[::-1]
ans = []
cost = 10**15
now = 0
for i,j in zip(dik(s,1),dik(t,2)):
    now = max(now,cost-i-j)
    ans.append(now)
print(*ans[:-1][::-1],sep="\n")

Solution (Python):
from heapq import heappush, heappop

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))
    
def dik(s,v):
    S = [float("INF")]*(n+1)
    S[s] = 0
    h = []
    heappush(h,[0,s])
    while h:
        d,now = heappop(h)
        for nex in e[now]:
            a,b = nex[0],nex[v]
            if d+b < S[a]:
                S[a] = d+b
                heappush(h,[d+b,a])
    return S
S = dik(s,1)
T = dik(t,2)
ans = [0]*(n)
cost = 10**15
now = 0
for i in range(n-1,-1,-1):
    now = max(now,cost-S[i+1]-T[i+1])
    ans[i] = now
print(*ans,sep="\n")

Solution (Python):
from heapq import heappush, heappop

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))

S = [float("INF")]*(n+1)
S[s] = 0
h = []
heappush(h,[0,s])
while h:
    d,now = heappop(h)
    for nex,a,b in e[now]:
        if d+a < S[nex]:
            S[nex] = d+a
            heappush(h,[d+a,nex])
T = [float("INF")]*(n+1)
T[t] = 0
h = []
heappush(h,[0,t])
while h:
    d,now = heappop(h)
    for nex,a,b in e[now]:
        if d+b < T[nex]:
            T[nex] = d+b
            heappush(h,[d+b,nex])

ans = [0]*(n+1)
cost = 10**15
now = 0
for i in range(n,0,-1):
    now = max(now,cost-S[i]-T[i])
    ans[i] = now
for i in ans[1:]:
    print(i)

Solution (Python):
from collections import deque

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))
S = [float("INF")]*(n+1)
S[s] = 0
q = deque([])
q.append([s,-1])
while q:
    now,bef = q.popleft()
    for nex,a,b in e[now]:
        if nex == bef:
            continue
        if S[now]+a < S[nex]:
            S[nex] = S[now]+a
            q.append([nex,now])
T = [float("INF")]*(n+1)
T[t] = 0
q = deque([])
q.append([t,-1])
while q:
    now,bef = q.popleft()
    for nex,a,b in e[now]:
        if nex == bef:
            continue
        if T[now]+b < T[nex]:
            T[nex] = T[now]+b
            q.append([nex,now])

ans = [0]*(n+1)
cost = 10**15
now = 0
for i in range(n,0,-1):
    now = max(now,cost-S[i]-T[i])
    ans[i] = now
for i in ans[1:]:
    print(i)