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.
from heapq import *
import numpy as np

class vertex:
    def __init__(self):
        self.list_adj = []  # list of [no_adjnode, a, b]

    def add_edge(self, adj):
        self.list_adj.append(adj)

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

s -= 1
t -= 1

# 
vertices = []
for i in range(n):
    v = vertex()
    vertices.append(v)

print(n, m, s, t)
# load node
for k in range(m):
    u, v, a, b = map(int, input().split())
    vertices[u-1].add_edge([v-1, a, b])
    vertices[v-1].add_edge([u-1, a, b])


#print('-----------------')

#print(n, m, s, t)

#    print(vertices[i].list_adj)

mode = 0
# return list of [no_adj, cost]
def get_adj(v):
    res = []
    for adj in v.list_adj:
        res.append([adj[0], adj[1+mode]])
    return res

#print('show adjcent(a)')
#for k in range(n):
#    print(get_adj(vertices[k]))

mode = 1
#print('show adjcent(b)')
#for k in range(n):
#    print(get_adj(vertices[k]))

def dijkstra(s):
    inf = 10e20
    dist = [inf] * n
    h = []
    heappush(h, (s, 0))
    while len(h) > 0:
        # pop 1 node
        v, dv = heappop(h)
        # if already decided, continue
        if dist[v] < inf:
            continue
        dist[v] = dv
        # push adjcent node
        list_adj = get_adj(vertices[v])
        for adj in list_adj:
            if dist[adj[0]] == inf:
                heappush(h, (adj[0], dv + adj[1]))
                pass
        pass
    return dist

mode = 0
dist_a = dijkstra(s)
mode = 1
dist_b = dijkstra(t)
cost = np.array(dist_a) + np.array(dist_b)
cost = np.array(cost, dtype='int')
#print(cost)

m0 = int(10e15)
for i in range(n):
    cost_available = cost[i:]
    print(m0-np.amin(cost_available))
from heapq import heappush, heappop

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

s -= 1
t -= 1

# 
vertices = []
for i in range(n):
  v = []
  vertices.append(v)

#print(n, m, s, t)
# load node
for k in range(m):
    u, v, a, b = map(int, input().split())
    vertices[u-1].append([v-1, a, b])
    vertices[v-1].append([u-1, a, b])


#print('-----------------')

#print(n, m, s, t)

#    print(vertices[i])

mode = 0
# return list of [no_adj, cost]
def get_adj(v):
    res = []
    for adj in vertices[v]:
        res.append([adj[0], adj[1+mode]])
    return res

#print('show adjcent(a)')
#for k in range(n):
#    print(get_adj(vertices[k]))

mode = 1
#print('show adjcent(b)')
#for k in range(n):
#    print(get_adj(vertices[k]))

def dijkstra(s):
    inf = int(10e20)
    dist_pre = [inf] * n
    dist = [inf] * n
    h = []
    heappush(h, (0, s))
    dist_pre[s] = 0
    while len(h) > 0:
        # pop 1 node
        dv, v = heappop(h)
        # if already decided, continue
        if dist[v] < inf:
            continue
        dist[v] = dv
        # push adjcent node
        list_adj = get_adj(v)
        #print(v, list_adj)
        for adj in list_adj:
            if dist[adj[0]] == inf:
                dnew = dv + adj[1]
                if dnew < dist_pre[adj[0]]:
                    dist_pre[adj[0]] = dnew
                    heappush(h, (dnew, adj[0]))
                pass
        pass
    return dist

mode = 0
dist_a = dijkstra(s)
mode = 1
dist_b = dijkstra(t)
cost = [a+b for a, b in zip(dist_a, dist_b)]
#cost = []
#for k in range(len(dist_a)):
#    cost.append(dist_a[k] + dist_b[k])
#cost = np.array(dist_a,dtype = 'int') + np.array(dist_b,dtype = 'int')
#cost = np.array(cost, dtype='int')
#print(dist_a)
#print(dist_b)
#print(cost)
#cost = np.array(cost, dtype='int')

res = [0]*n

min_temp = int(1e20)
m0 = int(1e15)
for i in range(n):
    k = n-1-i
    if(cost[k]<min_temp):
        min_temp = cost[k]
    res[k] = m0 - min_temp
    #cost_available = cost[i:]
    #print(m0-np.amin(cost_available))

for r in res:
    print(r)