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

Solution (Python):
from heapq import heappush,heappop
n,m,s,t=map(int,input().split())
a,b=[[]for i in range (n+1)],[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=(int(i) for i in input().split())
    a[p].append((q,r))
    a[q].append((p,r))
    b[p].append((q,g))
    b[q].append((p,g))
def f(x,r):
    p=[float("inf")for i in range(n+1)]
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p
s1,t1,p=f(s,a),f(t,b),[]
for i in range(1,n+1):
    p.append((s1[i]+t1[i],i))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,s,t = LI()
graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = LI()
    graph1[u-1].append((v-1,a))
    graph1[v-1].append((u-1,a))
    graph2[u-1].append((v-1,b))
    graph2[v-1].append((u-1,b))

def dijkstra(s,graph):
    d = [inf]*n
    d[s] = 0
    h = [(0,s)]
    while h:
        c,v = heappop(h)
        if d[v] < c:
            continue
        for t,cost in graph[v]:
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heappush(h,(d[t],t))
    return d

c1 = dijkstra(s-1,graph1)
c2 = dijkstra(t-1,graph2)
c = [c1[i] + c2[i] for i in range(n)]
money = 10**15
mi = c[-1]
for i in range(n-1)[::-1]:
    mi = min(mi,c[i])
    c[i] = mi
for i in range(n):
    print(money - c[i])

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

costm = [float('inf')]*n
costs = [float('inf')]*n
costm[s-1],costs[t-1] = 0,0

queue = deque([s-1])
while queue.__len__() > 0:
    p = queue.popleft()
    for a,b in edgem[p]:
        if costm[a] > costm[p] + b:
            costm[a] = costm[p] + b
            queue.append(a)
queue = deque([t-1])
while queue.__len__() > 0:
    p = queue.popleft()
    for a,b in edges[p]:
        if costs[a] > costs[p] + b:
            costs[a] = costs[p] + b
            queue.append(a)
ans = [float('inf')]*n
for i in range(n):
    ans[i] = costm[i] + costs[i]
for i in range(n-1,0,-1):
    ans[i-1] = min(ans[i-1],ans[i])
money = 10**15
for i in ans:
    print(money-i)

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

g_snk=[[] for _ in [0]*n]
[g_snk[u-1].append([v-1,b]) for u,v,a,b in uvab]
[g_snk[v-1].append([u-1,b]) for u,v,a,b in uvab]

import heapq
def dijkstra(g,start):
    inf=10**15
    dist=[inf for _ in [0]*n]
    h=[(0,start)]
    heapq.heapify(h)
    while h:
        d,i=heapq.heappop(h)
        if dist[i]==inf:
            dist[i]=d
            for x,y in g[i]:
                heapq.heappush(h,(d+y,x))
    return dist

yen=dijkstra(g_yen,s-1)
snk=dijkstra(g_snk,t-1)

cost=[yen[i]+snk[i] for i in range(n)]
m=cost[-1]
for i in range(n-1,-1,-1):
    m=min(m,cost[i])
    cost[i]=m
    
for i in cost:
    print(10**15-i)

Solution (Python):
import sys
input = sys.stdin.readline
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
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

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

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

Solution (Python):
import sys
input = sys.stdin.readline
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
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

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

d1 += d2
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]

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

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E[u1].items():
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = [dict() for _ in range(n)]
p2 = [dict() for _ in range(n)]
for i in range(m):
  p[u[i]-1][v[i]-1] = a[i]
  p[v[i]-1][u[i]-1] = a[i]
  p2[u[i]-1][v[i]-1] = b[i]
  p2[v[i]-1][u[i]-1] = b[i]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

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

Solution (Python):

from collections import defaultdict
import heapq

def get_dikstra(graph_data, weigh_data, node_num, start):
    dist_data = [-1 for i in range(node_num + 1)]
    check_num = [(0, start)]

    while len(check_num) > 0:
        now_dist, now_node = heapq.heappop(check_num)
        if dist_data[now_node] != -1:
            continue
        dist_data[now_node] = now_dist
        for next_node in graph_data[now_node]:
            if dist_data[next_node] != -1:
                continue
            heapq.heappush(check_num, (now_dist + weigh_data[(now_node, next_node)], next_node))

    return dist_data


def main():
    node_num, edge_num, start, goal = map(int, input().split())
    graph_data = defaultdict(set)
    yen_data = defaultdict(int)
    knoke_data = defaultdict(int)

    for i in range(edge_num):
        a, b, c, d = map(int, input().split())
        graph_data[a].add(b)
        graph_data[b].add(a)
        yen_data[(a, b)] = c
        yen_data[(b, a)] = c
        knoke_data[(a, b)] = d
        knoke_data[(b, a)] = d

    yen_dist = get_dikstra(graph_data, yen_data, node_num, start)
    knoke_dist = get_dikstra(graph_data, knoke_data, node_num, goal)

    ans_list = [0 for i in range(node_num + 1)]

    ans_list[node_num] = yen_dist[node_num] + knoke_dist[node_num]
    for i in range(1, node_num)[::-1]:
        ans_list[i] = min(ans_list[i + 1], yen_dist[i] + knoke_dist[i])

    first = 10 ** 15
    for i in range(1, node_num + 1):
        print(first - ans_list[i])





if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop, heappush

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

N, M, s, t = inpl()
Gs = [[] for _ in range(N+1)]
Gt = [[] for _ in range(N+1)]

for i in range(M):
    u, v, a, b = inpl()
    Gs[u].append([v, a])
    Gs[v].append([u, a])
    Gt[u].append([v, b])
    Gt[v].append([u, b])

S = [10**15]*(N+1)
T = [10**15]*(N+1)
S[s] = 0
T[t] = 0

Q = []
heappush(Q, [0, s])

while Q:
    pc, p = heappop(Q)
    if pc > S[p]:
        continue
    for q, dc in Gs[p]:
        if S[q] > pc + dc:
            S[q] = pc + dc
            heappush(Q, [S[q], q])

Q = []
heappush(Q, [0, t])

while Q:
    pc, p = heappop(Q)
    if pc > T[p]:
        continue
    for q, dc in Gt[p]:
        if T[q] > pc + dc:
            T[q] = pc + dc
            heappush(Q, [T[q], q])

tmp = 0
X = 10**15
ans = [0 for _ in range(N)]
for i in range(N, 0, -1):
    t = X - T[i] - S[i]
    tmp = max(tmp, t)
    ans[i-1] = tmp*1

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

Solution (Python):

import heapq
n,m,s,t = map(int,input().split())
UVAB = [list(map(int,input().split())) for _ in [0]*m]

Ea = [{} for _ in [0]*n]
Eb = [{} for _ in [0]*n]
for u,v,a,b in UVAB:
    Ea[u-1][v-1] = a
    Ea[v-1][u-1] = a
    Eb[u-1][v-1] = b
    Eb[v-1][u-1] = b


def Dijkstra(N,E,start):
    """
    N: ノード数
    E: 辺(dictのlist)
    start:開始ノード番号(0-indexed)
    """
    d = [-1]*N
    q = [(0,start-1)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d

da = Dijkstra(n,Ea,s)
db = Dijkstra(n,Eb,t)

C = [a+b for a,b in zip(da,db)]

ans = [C[-1]]
for c in C[-2::-1]:
    ans.append(min(ans[-1],c))

for out in ans[::-1]:
    print(10**15-out)

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


def dijkstra(adj, start):
    
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist


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

min_dist_yen = dijkstra(adj_yen, start)
min_dist_snuuk = dijkstra(adj_snuuk, goal)
lose = [float('inf')] * n
for i in range(1, n+1):
    lose[-i] = min(lose[-i+1], min_dist_yen[n-i+1] + min_dist_snuuk[n-i+1])

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

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

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

MON = 10**15
n, m, s, t = map(int, input().split())
V = list(range(1, n+1))
E1, E2 = {v: {} for v in V}, {v: {} for v in V}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    E1[u][v] = a
    E1[v][u] = a
    E2[u][v] = b
    E2[v][u] = b
ans = [MON]*n
dist_yen = dijkstra(V, E1, s)
dist_snuuk = dijkstra(V, E2, t)
temp = float('inf')
for v in V[::-1]:
    temp = min(temp, dist_yen[v] + dist_snuuk[v])
    ans[v-1] -= temp
print(*ans, sep='\n')

Solution (Python):
from heapq import heappop, heappush
INF = float('inf')

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

graph = [[] for _ in range(n + 1)]
for u, v, a, b in edges:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(s, pay):
    """
    s: start
    pay: 0 = yen, 1 = snuuk
    """
    d = [INF] * (n + 1)
    visited = [False] * (n + 1)
    pq = []

    heappush(pq, (0, s))
    d[s] = 0
    visited[s] = True

    while pq:
        cost, x = heappop(pq)
        visited[x] = True

        for v, *c in graph[x]:
            if visited[v]:
                continue

            if d[v] > d[x] + c[pay]:
                d[v] = d[x] + c[pay]
                heappush(pq, (d[v], v))

    return d

d1 = dijkstra(s, 0)
d2 = dijkstra(t, 1)

ans = []
tmp = float('inf')
for i in reversed(range(1, n + 1)):
    tmp = min(tmp, d1[i] + d2[i])
    ans.append(10 ** 15 - tmp)
    
print(*ans[::-1], sep='\n')

Solution (Python):
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, VC):
    color = [WHITE for i in range(N)]
    d = [INFTY for i in range(N)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

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

da = dijkstra(S-1, VA)
db = dijkstra(T-1, VB)
tmp = 10**16
base = 10 ** 15
ans = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = min(da[i] + db[i], tmp)
    ans[i] = tmp

for i in range(N):
    print(base - ans[i])

Solution (Python):
from heapq import *
n,m,s,t = map(int,input().split())
uvab = [list(map(int,input().split())) for _ in [0]*m]
connect = [[] for _ in [0]*n]
for u,v,a,b in uvab:
    connect[u-1].append((v-1,a,b))
    connect[v-1].append((u-1,a,b))
da = [-1]*n
db = [-1]*n
q = [(0,s-1)]
while q:
    c,i = heappop(q)
    if da[i]!=-1:continue
    da[i] = c
    for j,a,_ in connect[i]:
        if da[j]==-1:
            heappush(q,(c+a,j))
q = [(0,t-1)]
while q:
    c,i = heappop(q)
    if db[i]!=-1:continue
    db[i] = c
    for j,_,b in connect[i]:
        if db[j]==-1:
            heappush(q,(c+b,j))
ans = [10**15]
for ca,cb in zip(da[::-1],db[::-1]):
    ans.append(min(ans[-1],ca+cb))
for out in ans[:0:-1]:
    print(10**15-out)

Solution (Python):
import sys
input=sys.stdin.readline
N,M,S,T=map(int,input().split())
S-=1
T-=1
from collections import defaultdict
branch=defaultdict(dict)
for i in range(M):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    branch[u][v]=(a,b)
    branch[v][u]=(a,b)
def dijk(s,x):
    dist=[float('inf')]*N
    dist[s]=0
    check={s}
    while len(check)>0:
        now=check.pop()
        for nex,d in branch[now].items():
            if dist[now]+d[x]<dist[nex]:
                check|={nex}
                dist[nex]=dist[now]+d[x]
    return dist
en=dijk(S,0)
snuuk=dijk(T,1)
ans=[0]*N
ans[N-1]=en[N-1]+snuuk[N-1]
for i in range(N-2,-1,-1):
    ans[i]=min(ans[i+1],en[i]+snuuk[i])
for i in range(N):
    print(10**15-ans[i])

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


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                new_d = k + d
                if distance[v] > new_d:
                    distance[v] = new_d
                    heappush(queue, (new_d, v))
        return distance


n, m, s, t = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in uvab:
    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 ans in ans_list[n:0:-1]:
    print(10 ** 15 - ans)

Solution (Python):
import heapq
INF = 10**15

n, m, s, t = [int(item) for item in input().split()]
yen = [[] for _ in range(n)]
snk = [[] for _ in range(n)]

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        return self.dist

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

yen_dijk = Dijkstra(yen)
snk_dijk = Dijkstra(snk)

yen_dist = yen_dijk.calc(s-1)
snk_dist = snk_dijk.calc(t-1)
 
ans = [0] * n
min_cost = 10**15
i = n-1
for yy, ss in zip(yen_dist[::-1], snk_dist[::-1]):
    min_cost = min(min_cost, yy + ss)
    ans[i] = min_cost
    i -= 1

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

Solution (Python):
from heapq import heappop, heappush
 
 
def dijkstra(costs, s, i):
    q = [(0, s)]
    while q:
        c, v = heappop(q)
        if costs[v] >= 0:
            continue
        costs[v] = c
        for link in links[v]:
            u = link[0]
            if costs[u] == -1:
                heappush(q, (c + link[i], u))
 
 
n, m, s, t = map(int, input().split())
links = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    links[u] += (v, a, b),
    links[v] += (u, a, b),

yen_costs = [-1] * (n+1)
snk_costs = [-1] * (n+1)
dijkstra(yen_costs, s, 1)
dijkstra(snk_costs, t, 2)
ansl = []
ans = 0

for i in range(1, n+1):
    cost = yen_costs[-i]+snk_costs[-i]
    m = 10**15 - cost
    if ans < m:
        ans = m
    ansl.append(ans)
for _ in range(n):
    print(ansl.pop())

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

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

g_a = [[] for i in range(n)]
g_b = [[] for i in range(n)]

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

d_a = dijkstra(g_a,n,s-1)
d_b = dijkstra(g_b,n,t-1)

d = []
for i in range(n):
    d.append(d_a[i]+d_b[i])

d.reverse()
ans = []
m = float('inf')
for i in range(n):
    m = min(m,d[i])
    ans.append(10**15-m)
ans.reverse()

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

Solution (Python):
from collections import defaultdict
import heapq
n, m, s, t = map(int, input().split())


class Graph():
    def __init__(self):
        self.graph = defaultdict(list)


    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))


class Dijkstra():
    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.queue = []
        heapq.heappush(self.queue, (self.dist[start], start))

        while self.queue:
            dist_u, u = heapq.heappop(self.queue)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heapq.heappush(self.queue, (alt, v))


    def shortest_dist(self, goal):
        return self.dist[goal]

    
    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


yen_max = 10 ** 15
cost = [0] * n
train_yen = Graph()
train_sno = Graph()
for i in range(m):
    u, v, a, b = map(int, input().split())
    train_yen.add_edge(u - 1, v - 1, a)
    train_yen.add_edge(v - 1, u - 1, a)
    train_sno.add_edge(u - 1, v - 1, b)
    train_sno.add_edge(v - 1, u - 1, b)

cost_yen = Dijkstra(train_yen, s - 1)
cost_sno = Dijkstra(train_sno, t - 1)
for i in range(n):
    cost[i] = yen_max - (cost_yen.dist[i] + cost_sno.dist[i])

ans = [yen_max] * n
ans[n - 1] = cost[n - 1]
for i in range(n - 2, -1, -1):
    ans[i] = max(ans[i + 1], cost[i])
print(*ans, sep="\n")

Solution (Python):
import sys
N, M, s, t = map(int, input().split())

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    inf = 10**10
    dist = [inf] * N
    Q = [(0, s)]
    decided = set()
    for _ in range(N):
        while True:
            dn, vn = hpp(Q)
            if vn not in decided:
                decided.add(vn)
                dist[vn] = dn
                break
        for vf, df in Edge[vn]:
            if vf not in decided:
                hp(Q, (dn + df, vf))
    return dist
        
        

Edge1 = [[] for _ in range(N)]
Edge2 = [[] for _ in range(N)]
geta = 10**6
for _ in range(M):
    u, v, a, b = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    Edge1[u].append((v, a))
    Edge1[v].append((u, a))
    Edge2[u].append((v, b))
    Edge2[v].append((u, b))

D1 = dijkstra(N, s-1, Edge1)
D2 = dijkstra(N, t-1, Edge2)

D = [d1 + d2 for d1, d2 in zip(D1, D2)]
for i in range(N-2, -1, -1):
   D[i] = min(D[i+1], D[i])

for d in D:
    print(10**15 - d)

Solution (Python):
from collections import deque

inf = float('inf')

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

have = 10 ** 15

es = [[] for _ in range(N)]


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

cost_a = [inf] * N
cost_a[S] = 0

q = deque()
q.append((S, 0))
while q:
    u, c = q.popleft()
    for v, a, _ in es[u]:
        if cost_a[v] > (c + a):
            cost_a[v] = (c + a)
            q.append((v, c + a))


cost_b = [inf] * N
cost_b[T] = 0

q = deque()
q.append((T, 0))
while q:
    u, c = q.popleft()
    for v, _, b in es[u]:
        if cost_b[v] > (c + b):
            cost_b[v] = (c + b)
            q.append((v, c + b))


cost = [None for _ in range(N)]
t = inf
for i in reversed(range(N)):
    
    
    t = min(t, cost_a[i] + cost_b[i])
    cost[i] = t
    
    



for i in range(N):
    print(have - cost[i])

Solution (Python):
import sys

from collections import deque, defaultdict, Counter; from heapq import heappush, heappop


from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)


"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m, s, t = wi()
uvab = mi(m)

dists = []
distt = []
for i in range(m):
    dists.append([uvab[i][0], uvab[i][1], uvab[i][2]])
    distt.append([uvab[i][0], uvab[i][1], uvab[i][3]])

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

inputs = dists
inputt = distt

gs = Graph()
gt = Graph()
for src, dst, weight in inputs:
    gs.add_edge(src, dst, weight)
    gs.add_edge(dst, src, weight)
for src, dst, weight in inputt:
    gt.add_edge(src, dst, weight)
    gt.add_edge(dst, src, weight)

spdi = {}
tpdi = {}
ds = Dijkstra(gs, s)
dt = Dijkstra(gt, t)
for i in range(1, n + 1):
    sp = format(ds.shortest_distance(i))
    spdi[i] = int(sp)
    tp = format(dt.shortest_distance(i))
    tpdi[i] = int(tp)


route = []
for i in range(1, n + 1):
    route.append([10 ** 15 - (spdi[i] + tpdi[i]), i])
route.sort(key=ig(0), reverse=True)
j = 0
for i in range(n):
    while j < n:
        if i < route[j][1]:
            print(route[j][0])
            break
        else:
            j += 1
    if j == n:
        print(route[j][0])