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 math import sin, cos, tan, asin, acos, atan, sqrt, floor, ceil, pi, log10, log, gcd, hypot
from itertools import accumulate, permutations, combinations
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from copy import deepcopy
from decimal import Decimal
import heapq
import sys

mod = 10**9 + 7



sys.setrecursionlimit(10**7)
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class BIT():
    
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def to_sum(self, i):
        
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        
        return self.to_sum(j)-self.to_sum(i-1)


class SegTree():
    
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


class LCA():

    def _bfs(self, node):
        self.visited[node] = True
        for p in tree[node]:
            if self.visited[p] == False:
                self.kprv[0][p] = node
                self.depth[p] = self.depth[node]+1
                self._bfs(p)

    def __init__(self, root, tree):
        self.root = root
        self.n = len(tree)-1
        self.K = (self.n-1).bit_length()
        self.visited = [False for i in range(self.n+1)]
        self.depth = [0 for i in range(self.n+1)]
        self.kprv = [[-1 for i in range(self.n+1)] for j in range(self.K+1)]
        self._bfs(self.root)
        for cnt in range(1, self.K+1):
            for node in range(self.n+1):
                if self.kprv[cnt-1][node] >= 0:
                    self.kprv[cnt][node] = self.kprv[cnt -
                                                     1][self.kprv[cnt-1][node]]
                else:
                    self.kprv[cnt][node] = -1

    def query(self, u, v):
        

        dd = self.depth[v]-self.depth[u]

        if dd < 0:
            u, v = v, u
            dd = -dd

        for i in range(self.K+1):
            if dd & 1:
                v = self.kprv[i][v]
            dd >>= 1
        if u == v:
            return u

        for i in range(self.K-1, -1, -1):
            pu = self.kprv[i][u]
            pv = self.kprv[i][v]
            if pu != pv:
                u = pu
                v = pv
        return self.kprv[0][u]


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


class Graph():
    def __init__(self, N, Type):
        self._V = N  
        self._E = 0  
        self.type = Type
        if Type == "D":
            
            self.G = [[] for i in range(self._V+1)]
        elif Type == "W":
            
            self.G = [[float("inf") for i in range(self._V+1)]
                      for j in range(self._V+1)]
        elif Type == "B" or Type == "K":
            
            self.G = []

    def E(self):
        """ 辺数 """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

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

        elif self.type == "W":
            self.G[_from][_to] = _cost

        elif self.type == "B" or self.type == "K":
            self.G.append((_from, _to, _cost))

    def add_both(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する (無向グラフ) """
        self.add(_from, _to, _cost)
        self.add(_to, _from, _cost)


class Dijkstra(Graph):
    def __init__(self, N):
        super().__init__(N, "D")
        self.d = [10**20]*(self._V + 1)
        self.que = []
        heapq.heapify(self.que)

    def shortest_path(self, s):
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[s] = 0
        heapq.heappush(self.que, (0, s))
        while self.que:
            cost, v = heapq.heappop(self.que)
            if self.d[v] < cost:
                continue

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


class Bellman_Ford(Graph):
    def __init__(self, N):
        super().__init__(N, "B")
        self.d = [10**20]*(self._V+1)

    def shortest_path(self, s):
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[s] = 0
        for _ in range(self._V):
            flag = False
            for From, To, cost in self.G:
                newlen = self.d[From]+cost
                if newlen < self.d[To]:
                    flag = True
                    self.d[To] = newlen
            if not flag:
                break
        return self.d

    @property
    def have_negative_circle(self):
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[1] = 0
        for i in range(1, self._V+1):
            flag = False
            for From, To, cost in self.G:
                newlen = self.d[From]+cost
                if newlen < self.d[To]:
                    flag = True
                    self.d[To] = newlen
            if not flag:
                break
            if i == self._V:
                return True
        return False


class Warshall_Floyd(Graph):

    def __init__(self, N):
        super().__init__(N, "W")

    @property
    def shortest_path(self):
        
        _N = self._V
        for i in range(_N+1):
            self.G[i][i] = 0
        for k in range(1, _N+1):
            for i in range(1, _N+1):
                for j in range(1, _N+1):
                    self.G[i][j] = min(self.G[i][j], self.G[i][k]+self.G[k][j])
        return self.G


class Kruskal(Graph):
    def __init__(self, N):
        super().__init__(N, "K")
        self.connected_G = UnionFind(self._V)

    @property
    def find_lowest_cost(self):
        res = 0
        self.G.sort()
        for p, q, cost in self.G:
            if not self.connected_G.same(p, q):
                self.connected_G.union(p, q)
                res += cost
        return res


def union_lcm(lists):
    if len(lists) == 1:
        return lists[0]
    elif len(lists) > 1:
        num = lists[0]
        for i in range(1, len(lists)):
            num = num*lists[i]//gcd(num, lists[i])
        return num


def union_gcd(lists):
    if len(lists) == 1:
        return lists[0]
    elif len(lists) > 1:
        num = lists[0]
        for i in range(1, len(lists)):
            num = gcd(num, lists[i])
        return num


def is_prime(N):
    for i in range(2, N+1):
        if i**2 > N:
            break
        if N % i == 0:
            return False
    return True


class Primes():
    def __init__(self, N):
        self.N = N
        self.prime = {i for i in range(2, self.N+1)}
        for i in range(2, self.N+1):
            if i in self.prime:
                for j in range(i*2, self.N+1, i):
                    if j in self.prime:
                        self.prime.remove(j)

    def show_primes(self):
        return self.prime

    def is_prime(self, X):
        if X < self.N:
            return X in self.prime
        else:
            return "Unknown"


def main():
    

    N, M, S, T = map(int, input().split())
    G1, G2 = Dijkstra(N), Dijkstra(N)
    for i in range(M):
        u, v, a, b = map(int, input().split())
        G1.add_both(u, v, b)
        G2.add_both(u, v, a)
    yen = G2.shortest_path(S)
    snuke = G1.shortest_path(T)

    minimum_case = [10**15 for i in range(N+1)]
    for i in range(N):
        minimum_case[1+i] -= (yen[i+1]+snuke[i+1])
    for i in range(N-1, -1, -1):
        minimum_case[i] = max(minimum_case[i], minimum_case[i+1])
    for i in range(1, N+1):
        print(minimum_case[i])


if __name__ == "__main__":
    main()

Solution (Python):


from math import sin, cos, tan, asin, acos, atan, sqrt, floor, ceil, pi, log10, log, gcd, hypot
from itertools import accumulate, permutations, combinations
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from copy import deepcopy
from decimal import Decimal
import heapq
import sys


sys.setrecursionlimit(10**7)
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class BIT():
    
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def to_sum(self, i):
        
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        
        return self.to_sum(j)-self.to_sum(i-1)


class SegTree():
    
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


class LCA():

    def _bfs(self, node):
        self.visited[node] = True
        for p in tree[node]:
            if self.visited[p] == False:
                self.kprv[0][p] = node
                self.depth[p] = self.depth[node]+1
                self._bfs(p)

    def __init__(self, root, tree):
        self.root = root
        self.n = len(tree)-1
        self.K = (self.n-1).bit_length()
        self.visited = [False for i in range(self.n+1)]
        self.depth = [0 for i in range(self.n+1)]
        self.kprv = [[-1 for i in range(self.n+1)] for j in range(self.K+1)]
        self._bfs(self.root)
        for cnt in range(1, self.K+1):
            for node in range(self.n+1):
                if self.kprv[cnt-1][node] >= 0:
                    self.kprv[cnt][node] = self.kprv[cnt -
                                                     1][self.kprv[cnt-1][node]]
                else:
                    self.kprv[cnt][node] = -1

    def query(self, u, v):
        

        dd = self.depth[v]-self.depth[u]

        if dd < 0:
            u, v = v, u
            dd = -dd

        for i in range(self.K+1):
            if dd & 1:
                v = self.kprv[i][v]
            dd >>= 1
        if u == v:
            return u

        for i in range(self.K-1, -1, -1):
            pu = self.kprv[i][u]
            pv = self.kprv[i][v]
            if pu != pv:
                u = pu
                v = pv
        return self.kprv[0][u]


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


class Graph():
    def __init__(self, N, M, Type):
        self._E = M  
        self._V = N  
        self.type = Type
        if Type == "D":
            
            self.G = [[] for i in range(self._V+1)]
        elif Type == "W":
            
            self.G = [[float("inf") for i in range(self._V+1)]
                             for j in range(self._V+1)]
        elif Type == "B" or Type == "K":
            
            self.G = []

    def E(self):
        """ 辺数 """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

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

        elif self.type == "W":
            self.G[_from][_to] = _cost

        elif self.type == "B" or self.type == "K":
            self.G.append((_from, _to, _cost))


class Dijkstra(Graph):
    def __init__(self,N,M,Type):
        super().__init__(N,M,Type)
        self.d = [10**20]*(self._V + 1)
        self.que = []

    def shortest_path(self, s):
        assert self.type == "D"
        heapq.heapify(self.que)
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[s] = 0
        heapq.heappush(self.que, (0, s))
        while self.que:
            cost, v = heapq.heappop(self.que)
            if self.d[v] < cost:
                continue

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


class Bellman_Ford(Graph):
    def __init__(self,N,M,Type):
        super().__init__(N,M,Type)
        self.d = [10**20]*(self._V+1)

    def shortest_path(self, s):
        assert self.type == "B"
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[s] = 0
        for _ in range(self._V):
            flag = False
            for From, To, cost in self.G:
                newlen = self.d[From]+cost
                if newlen < self.d[To]:
                    flag = True
                    self.d[To] = newlen
            if not flag:
                break
        return self.d

    def have_negative_circle(self):
        assert self.type == "B"
        for i in range(self._V+1):
            self.d[i] = 10**20
        self.d[1] = 0
        for i in range(1, self._V+1):
            flag = False
            for From, To, cost in self.G:
                newlen = self.d[From]+cost
                if newlen < self.d[To]:
                    flag = True
                    self.d[To] = newlen
            if not flag:
                break
            if i == self._V:
                return True
        return False


class Warshall_Floyd(Graph):

    def __init__(self,N,M,Type):
        super().__init__(N,M,Type)
        self.d = [[10**20 for i in range(self._V+1)] for j in range(self._V+1)]

    def shortest_path(self):
        assert self.type == "W"
        _N = self._V
        for i in range(_N+1):
            for j in range(_N+1):
                self.d[i][j] = self.G[i][j]
        for i in range(_N+1):
            self.d[i][i] = 0
        for k in range(1, _N+1):
            for i in range(1, _N+1):
                for j in range(1, _N+1):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k]+self.d[k][j])
        return d


class Kruskal(Graph):
    def __init__(self,N,M,Type):
        super().__init__(N,M,Type)

    def find_lowest_cost(self):
        res = 0
        self.G.sort()
        connected_G = UnionFind(self._V)
        for p, q, cost in self.G:
            if not connected_G.same(p, q):
                connected_G.union(p, q)
                res += cost
        return res


def union_lcm(lists):
    if len(lists) == 1:
        return lists[0]
    elif len(lists) > 1:
        num = lists[0]
        for i in range(1, len(lists)):
            num = num*lists[i]//gcd(num, lists[i])
        return num


def union_gcd(lists):
    if len(lists) == 1:
        return lists[0]
    elif len(lists) > 1:
        num = lists[0]
        for i in range(1, len(lists)):
            num = gcd(num, lists[i])
        return num


def is_prime(N):
    for i in range(2, N+1):
        if i**2 > N:
            break
        if N % i == 0:
            return False
    return True


class Primes():
    def __init__(self, N):
        self.N = N
        self.prime = {i for i in range(2, self.N+1)}
        for i in range(2, self.N+1):
            if i in self.prime:
                for j in range(i*2, self.N+1, i):
                    if j in self.prime:
                        self.prime.remove(j)

    def show_primes(self):
        return self.prime

    def is_prime(self, X):
        if X < self.N:
            return X in self.prime
        else:
            return "Unknown"


def main():
    

    N, M, S, T = map(int, input().split())
    G1, G2 = Dijkstra(N, M, "D"), Dijkstra(N, M, "D")
    for i in range(M):
        u, v, a, b = map(int, input().split())
        G2.add(u, v, a)
        G2.add(v, u, a)
        G1.add(u, v, b)
        G1.add(v, u, b)
    yen=G2.shortest_path(S)
    snuke=G1.shortest_path(T)
    minimum_case=[10**15 for i in range(N+1)]
    for i in range(N):
        minimum_case[1+i] -= (yen[i+1]+snuke[i+1])
    for i in range(N-1, -1, -1):
        minimum_case[i]=max(minimum_case[i], minimum_case[i+1])
    for i in range(1, N+1):
        print(minimum_case[i])
    return


if __name__ == "__main__":
    main()

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

import heapq
def dijkstra_heap(s,graph):
  
  dist=[float("inf")]*size_v
  prev=[-1]*size_v
  used=[False]*size_v
  
  dist[s]=0
  used[s]=True
  

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    
    if used[min_v]:
    
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used[min_v]=True
    
    for v,w in graph[min_v]:
      if not used[v]: 
      
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

graph_yen=[[] for _ in range(n+1)]
graph_snu=[[] for _ in range(n+1)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  graph_yen[u].append((v,a))
  graph_yen[v].append((u,a))
  graph_snu[u].append((v,b))
  graph_snu[v].append((u,b))
  
size_v=n+1
dist_yen,prev_yen=dijkstra_heap(s,graph_yen)
dist_snu,prev_snu=dijkstra_heap(t,graph_snu)



cost_list=[0]*(n+1)
cost_list[n]=dist_yen[n]+dist_snu[n]
for i in reversed(range(1,n)):
  cost_list[i]=min(cost_list[i+1],dist_yen[i]+dist_snu[i])


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

Solution (Python):
from heapq import *
N,M,S,T=map(int,input().split())
S,T=S-1,T-1
u,v,a,b=0,0,0,0
Gy=[[] for i in range(N)]
Gs=[[] for i in range(N)]
for i in range(M):
  u,v,a,b=map(int,input().split())
  u,v=u-1,v-1
  Gy[v].append((u,a))
  Gy[u].append((v,a))
  Gs[v].append((u,b))
  Gs[u].append((v,b))
Dy=[0]*N
Ds=[0]*N
INF=10**15
def ijk(s,D,G):
  global INF
  for i in range(len(D)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(S,Dy,Gy)
ijk(T,Ds,Gs)
Q=[Dy[i]+Ds[i] for i in range(N)]
P=[INF]
for i in range(N):
  P.append(min(P[i],Q[-i-1]))
for i in range(N):
  print(INF-P[-i-1])