Buggy python submission (verdict: Time Limit Exceeded):
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
		for v,yen,snuuk in nl[u]:
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+snuuk

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
		for v,yen,snuuk in nl[u]:
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+snuuk

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

D=[]

for i in range(1,n+1):
	D.append( (d_y[i]+d_s[i], i ) ) 



D.sort(key=lambda x: x[0])


t=1
for x,N in D:
	for j in range(t,N+1):
		#print j,x
		print 10**15-x
		t+=1
		if t==n+1:
			quit()
	


Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#Dijkstra yen
d_y=[ float("inf") ]*(n+1)
d_y[s]=0

Q=[]
heapq.heappush(Q,s)

while Q:
	u=heapq.heappop(Q)
	for v,yen,snuuk in nl[u]:
		alt=d_y[u]+yen
		if d_y[v]> alt:
			d_y[v]=alt
			heapq.heappush(Q,v)

#Dijkstra snuuk
d_s=[ float("inf")]*(n+1)
d_s[t]=0

Q=[]
heapq.heappush(Q,t)

while Q:
	u=heapq.heappop(Q)
	for v,yen,snuuk in nl[u]:
		alt=d_s[u]+snuuk
		if d_s[v]> alt:
			d_s[v]=alt
			heapq.heappush(Q,v)


val=float("inf")
A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#Dijkstra yen
d_y=[ float("inf") ]*(n+1)
d_y[s]=0

Q=[]
heapq.heappush(Q,s)

while Q:
	u=heapq.heappop(Q)
	for i in nl[u]:
		v=i[0]
		yen=i[1]
		alt=d_y[u]+yen
		if d_y[v]> alt:
			d_y[v]=alt
			heapq.heappush(Q,v)

#Dijkstra snuuk
d_s=[ float("inf")]*(n+1)
d_s[t]=0

Q=[]
heapq.heappush(Q,t)

while Q:
	u=heapq.heappop(Q)
	for i in nl[u]:
		v=i[0]
		snuuku=i[2]
		alt=d_s[u]+snuuku
		if d_s[v]> alt:
			d_s[v]=alt
			heapq.heappush(Q,v)


val=float("inf")
A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf")]*(n+1)
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
import  heapq

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Runtime Error):
import  heapq

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

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


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while Q:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print(10**15-i)

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while Q:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i


Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)

Buggy python submission (verdict: Time Limit Exceeded):
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

D=[]

for i in range(1,n+1):
	D.append( (d_y[i]+d_s[i], i ) ) 



D.sort(key=lambda x: x[0])


t=1
for x,N in D:
	for j in range(t,N+1):
		#print j,x
		print 10**15-x
		t+=1
		if t==n+1:
			quit()


Fixed submission:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)