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
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright



import sys
import heapq
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright






n,m,s,t=map(int,input().split())
s-=1;t-=1
def dijkstra(s,G):
    dist=[inf for i in range(n)] 
    dist[s]=0
    mirai=[True for i in range(n)] 
    mirai[s]=False

    queue=[] 
    for kyori,to in G[s]:
        heapq.heappush(queue , kyori*10**6+to)  
    while queue:
        minedge= heapq.heappop(queue)
        
        if not mirai[minedge%(10**6)]: continue
        
        v=minedge%(10**6) 
        dist[v] = minedge//(10**6) 
        mirai[v]=False
        for kyori,to in G[v]:
            if mirai[to]:
                heapq.heappush(queue, (kyori+dist[v])*(10**6)+to)
                
    return dist

G1= [[] for i in range(n)]
G2= [[] for i in range(n)]
for  i in range(m):
    a,b,y,p=map(int,input().split())
    a-=1;b-=1
    G1[a].append((y,b))
    G1[b].append((y,a))
    G2[a].append((p,b))
    G2[b].append((p,a))
A=dijkstra(s,G1)
B=dijkstra(t,G2)
C=[i+j for i,j in zip(A,B)]
ANS=[0]*(n) ; ANS[-1]=C[-1]
for i in range(n-2,-1,-1):
    ANS[i]= min(ANS[i+1], C[i])
for i in range(n):
    print(10**15-ANS[i])

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

def main():
  n, m, s, t = map(int, input().split())
  
  inf = pow(10, 15)
  
  tree = [[] for _ in range(n)]
  for i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u-1].append((v-1, a, b))
    tree[v-1].append((u-1, a, b))
  
  ans_yen = [0]*n
  ans_snuke = [0]*n
  
  for start, ans in zip([s-1, t-1], [ans_yen, ans_snuke]):
    already = [False]*n
    not_yet = [(0, start)]
    
    while len(not_yet) > 0:
      c, p = heappop(not_yet)
      if already[p]:
        continue
      ans[p] = c
      already[p] = True
      
      for (value, a, b) in tree[p]:
        if already[value]:
          continue
        if start == s-1:
          cost = a
        else:
          cost = b
        heappush(not_yet, (c+cost, value))
  
  ans = [0]*n
  sub = inf
  for i in range(n-1, -1, -1):
    sub = min(sub, ans_yen[i]+ans_snuke[i])
    ans[i] = sub
  
  sub = inf
  for a in ans:
    print(sub-a)
      
  
  
  
if __name__ == "__main__":
  main()

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

def main():
  n, m, s, t = map(int, input().split())
  
  inf = pow(10, 15)
  
  tree = [[] for _ in range(n)]
  for i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u-1].append((v-1, a, b))
    tree[v-1].append((u-1, a, b))
  
  ans_yen = [0]*n
  ans_snuke = [0]*n
  
  for start, ans in zip([s-1, t-1], [ans_yen, ans_snuke]):
    already = [False]*n
    not_yet = [(0, start)]
    
    while len(not_yet) > 0:
      c, p = heappop(not_yet)
      if already[p]:
        continue
      ans[p] = c
      already[p] = True
      
      for (value, a, b) in tree[p]:
        if already[value]:
          continue
        if start == s-1:
          cost = a
        else:
          cost = b
        heappush(not_yet, (c+cost, value))
  
  ans = [0]*n
  sub = inf
  for i in range(n-1, -1, -1):
    sub = min(sub, ans_yen[i]+ans_snuke[i])
    ans[i] = sub
  
  sub = inf
  for a in ans:
    print(sub-a)
      
  
  
  
if __name__ == "__main__":
  main()

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


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

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

e1 = [[] for _ in range(n)]
e2 = [[] for _ in range(n)]
for i in range(m):
    a,b,en,su = uvab[i]
    a,b = a-1, b-1
    e1[a].append((en, b))
    e1[b].append((en, a))
    e2[a].append((su, b))
    e2[b].append((su, a))

c1=dijkstra(s-1,e1)
c2=dijkstra(t-1,e2)


hlst=[]
for i in range(n):
    hlst.append((c1[i]+c2[i],i))

heapq.heapify(hlst)

for i in range(n):
    while hlst[0][1]<i:
        heapq.heappop(hlst)
    print(10**15-hlst[0][0])

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    from collections import defaultdict
    INF = float('INF')

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

    edge = defaultdict(list)

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

    dist_s = defaultdict(lambda: float("INF"))
    dist_t = defaultdict(lambda: float("INF"))

    dist_s[s] = 0
    dist_t[t] = 0

    hq = []
    heapq.heappush(hq, (0, s))

    while hq:
        cost, cur = heapq.heappop(hq)
        for nx, a, _ in edge[cur]:
            nc = cost + a
            if nc < dist_s[nx]:
                dist_s[nx] = nc
                heapq.heappush(hq, (nc, nx))

    heapq.heappush(hq, (0, t))

    while hq:
        cost, cur = heapq.heappop(hq)
        for nx, _, b in edge[cur]:
            nc = cost + b
            if nc < dist_t[nx]:
                dist_t[nx] = nc
                heapq.heappush(hq, (nc, nx))

    res = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        res[i] = max(res[i + 1], 10 ** 15 - (dist_s[i + 1] + dist_t[i + 1]))

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

def dijkstra(G, s=0):
    n = len(G)
    que = [(0, s)]
    dist = [INF] * n
    dist[s] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for v, c in G[u]:
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(que, (dist[u] + c, v))
    return dist

n, m, s, t = LI()
s-=1
t-=1
G1 = [[] for _ in range(n)]
G2 = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = LI()
    G1[u-1] += [(v-1, a)]
    G1[v - 1] += [(u - 1, a)]
    G2[u-1] += [(v-1, b)]
    G2[v - 1] += [(u - 1, b)]

y_cost = dijkstra(G1, s)
s_cost = dijkstra(G2, t)
ans = [0] * n
ret = INF
for i in range(n - 1, -1, -1):
    ret = min(ret, s_cost[i] + y_cost[i])
    ans[i] = 10**15 - ret

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

Solution (Python):
from heapq import heappush, heappop
def Dijkstra(edge,r,i):
  d=[INF]*len(edge) 
  que=[]
  heappush(que,(0,r))
  d[r]=0
  while que:
    dist,node=heappop(que)
    for to,*cost in edge[node]:
      if d[to]>cost[i]+dist:
        d[to]=cost[i]+dist
        heappush(que,(d[to],to))
  return d
n,m,s,t=map(int,input().split())
e=[[] for _ in range(n+1)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  e[u]+=[(v,a,b)]
  e[v]+=[(u,a,b)]
INF=10**18
di=Dijkstra(e,s,0)
dj=Dijkstra(e,t,1)
d=sorted(enumerate([i+j for i,j in zip(di,dj)]),key=lambda x:x[1])[::-1]
for i in range(n):
  while d[-1][0]<=i:d.pop()
  print(10**15-d[-1][1])

Solution (Python):
import heapq
INF = float('inf')


def dijkstra(s, n, edges, d):
    d = [INF] * n
    d[s] = 0
    pq = [(0, s)]
    while len(pq):
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for v2nvcost, nv in edges[v]:
            if c + v2nvcost < d[nv]:
                d[nv] = c + v2nvcost
                heapq.heappush(pq, (d[nv], nv))
    return d


n, m, s, t = map(int, input().split())
s -= 1
t -= 1
edges_yen = [[] for _ in range(n)]
edges_snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edges_yen[u].append((a, v))
    edges_yen[v].append((a, u))
    edges_snuuk[u].append((b, v))
    edges_snuuk[v].append((b, u))
d = [INF] * n
d_yen = dijkstra(s, n, edges_yen, d)
d = [INF] * n
d_snuuk = dijkstra(t, n, edges_snuuk, d)
temp = [0] * n  
for i in range(n):
    temp[i] = 10**15 - (d_yen[i] + d_snuuk[i])

ans = [INF] * n
ans[-1] = temp[-1]
for i in range(n - 2, -1, -1):
    ans[i] = max(ans[i + 1], temp[i])


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

Solution (Python):
import heapq
INF = float('inf')


def dijkstra(s, n, edges, d):
    d = [INF] * n
    d[s] = 0
    pq = [(0, s)]
    while len(pq):
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for v2nvcost, nv in edges[v]:
            if c + v2nvcost < d[nv]:
                d[nv] = c + v2nvcost
                heapq.heappush(pq, (d[nv], nv))
    return d


n, m, s, t = map(int, input().split())
s -= 1
t -= 1
edges_yen = [[] for _ in range(n)]
edges_snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edges_yen[u].append((a, v))
    edges_yen[v].append((a, u))
    edges_snuuk[u].append((b, v))
    edges_snuuk[v].append((b, u))
d = [INF] * n
d_yen = dijkstra(s, n, edges_yen, d)
d = [INF] * n
d_snuuk = dijkstra(t, n, edges_snuuk, d)
temp = [0] * n  
for i in range(n):
    temp[i] = 10**15 - (d_yen[i] + d_snuuk[i])

ans = [INF] * n
ans[-1] = temp[-1]
for i in range(n - 2, -1, -1):
    ans[i] = max(ans[i + 1], temp[i])


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

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

def main():
    import collections
    import heapq

    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 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 = MI()

    G1 = Dijkstra()  
    G2 = Dijkstra()  

    for i in range(m):
        u,v,a,b = MI()
        G1.add(u,v,a)
        G2.add(u,v,b)

    D1 = G1.search(s)
    D2 = G2.search(t)

    A = []

    for i in range(1, n + 1):
        A.append((D1[i] + D2[i], i))

    A.sort()

    b = 0
    for i in range(n):
        if i == 0:
            print(10 ** 15 - A[i][0])
        elif i < A[b][1]:
            print(10 ** 15 - A[b][0])
        else:
            while i >= A[b][1]:
                b += 1
            print(10 ** 15 - A[b][0])

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

def dijkstra(s, edge):
    '''
    始点sから各頂点への最短距離を求める
    '''
    d = [float("inf")] * n
    d[s] = 0
    used = [False] * n
    used[s] = True
    edgelist = []

    for e in edge[s]:
        heappush(edgelist, e)

    while edgelist:
        cost, v = heappop(edgelist)
        if used[v]:
            continue
        d[v] = cost
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])

    return d


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

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

d1 = dijkstra(s-1, e1)
d2 = dijkstra(t-1, e2)
dist = [d1[i] + d2[i] for i in range(n)]

res = [0] * n

min_dist = float('inf')
for i in range(n-1, -1, -1):
    min_dist = min(min_dist, dist[i])
    res[i] = 10 ** 15 - min_dist

for v in res:
    print(v)

Solution (Python):
from heapq import heappush, heappop

def dijkstra(s, edge):
    '''
    始点sから各頂点への最短距離を求める
    '''
    d = [float("inf")] * n
    d[s] = 0
    used = [False] * n
    used[s] = True
    edgelist = []

    for e in edge[s]:
        heappush(edgelist, e)

    while edgelist:
        cost, v = heappop(edgelist)
        if used[v]:
            continue
        d[v] = cost
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])

    return d


def segfunc(x, y):
    '''
    問題に応じて返り値を設定
    '''
    return min(x, y)


def init(a):
    '''
    配列aで初期化
    '''
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])


def update(k, x):
    '''
    a[k]の値をxに更新
    '''
    k += num - 1
    seg[k] = x
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k*2+1], seg[k*2+2])


def query(p, q):
    '''
    [p, q)についてsegfuncを適用したものを返す
    '''
    if q <= p:
        return ide_ele
    
    p += num - 1
    q += num - 2
    res = ide_ele

    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(res, segfunc(seg[p], seg[q]))
    
    return res


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

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

d1 = dijkstra(s-1, e1)
d2 = dijkstra(t-1, e2)
dist = [d1[i] + d2[i] for i in range(n)]

num = (2 ** len(bin(n - 1)) - 2)
ide_ele = float('inf')
seg = [ide_ele] * 2 * num
init(dist)

for i in range(n):
    print(10 ** 15 - query(i, n))

Solution (Python):
import numpy as np
from heapq import heappush, heappop

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




d = []
for i in range(n+1):
    d.append(d1[i]+d2[i])


ans = []
B = 10**15
for i in range(n):
    B = min(B, d[n-i])
    ans.append(B)
ans = ans[::-1]

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

Solution (Python):
import heapq

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

INF = float("inf")
YEN = pow(10,15)
n,m,s,t = map(int,input().split())
s-=1;t-=1 
yedge = [[] for _ in range(n)]
sedge = [[] for _ in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  u-=1;v-=1
  yedge[u].append([a,v]);yedge[v].append([a,u])
  sedge[u].append([b,v]);sedge[v].append([b,u])

def dijkstra_heap(s,edge):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]: 
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False 
        for e in edge[v]:
            if used[e[1]]: 
                heapq.heappush(edgelist,[e[0]+d[v],e[1]]) 
    return d 
yto = dijkstra_heap(s,yedge)


sot = dijkstra_heap(t,sedge)




A = []
for i in range(n):
  if i == s:
    temp = sot[i]
  elif i == t:
    temp = yto[i]
  else:
    temp = yto[i]+sot[i]
  A.append(temp)

Tree = SegmentTree(A,min, INF)
for i in range(n):
  temp = Tree.sum(i,n)
  ans = YEN - temp
  print(ans)