Buggy python submission (verdict: Time Limit Exceeded):
n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]


checktown=s
checked=set()
alltown=set(list(range(1,n+1)))

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]


    checked=checked|{checktown}
    YENcheck=10**16

    for i in (alltown - checked):
        if YENcheck>YEN[i]:
            YENcheck=YEN[i]
            checktown=i




checktown=t
checked=set()
alltown=set(list(range(1,n+1)))

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]


    checked=checked|{checktown}
    SNOOKcheck=10**16

    for i in (alltown - checked):
        if SNOOKcheck>SNOOK[i]:
            SNOOKcheck=SNOOK[i]
            checktown=i



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

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

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

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

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

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

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]


checktown=s
checked=set()
alltown=set(list(range(1,n+1)))
checking=[(0,s)]

while checking:

    checktown=heapq.heappop(checking)[1]
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]
            heapq.heappush(checking,(i[1],i[0]))


    checked=checked|{checktown}
    

checktown=t
checked=set()
alltown=set(list(range(1,n+1)))
checking=[(0,t)]

while checking:

    checktown=heapq.heappop(checking)[1]
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]
            heapq.heappush(checking,(i[2],i[0]))

    checked=checked|{checktown}
    


MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

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

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]


checktown=s
checked=set()
alltown=set(list(range(1,n+1)))
checking=[(0,s)]

while checked != alltown:

    checktown=heapq.heappop(checking)[1]
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]
            heapq.heappush(checking,(i[1],i[0]))


    checked=checked|{checktown}
    

checktown=t
checked=set()
alltown=set(list(range(1,n+1)))
checking=[(0,t)]

while checked != alltown:

    checktown=heapq.heappop(checking)[1]
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]
            heapq.heappush(checking,(i[2],i[0]))

    checked=checked|{checktown}
    


MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

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

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]


checktown=s
checked=set()
alltown=set(list(range(1,n+1)))
checking=[(0,s)]

while checked != alltown:

    checktown=heapq.heappop(checking)[1]
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]
            heapq.heappush(checking,(i[1],i[0]))


    checked=checked|{checktown}
    

checktown=t
checked=set()
alltown=set(list(range(1,n+1)))
checking=[(0,t)]

while checked != alltown:

    checktown=heapq.heappop(checking)[1]
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]
            heapq.heappush(checking,(i[2],i[0]))

    checked=checked|{checktown}
    


MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

Buggy python submission (verdict: Time Limit Exceeded):
n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]


checktown=s
checked=set()
alltown=set(list(range(1,n+1)))

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]


    checked=checked|{checktown}
    YENcheck=10**16

    for i in (alltown - checked):
        if YENcheck>YEN[i]:
            YENcheck=YEN[i]
            checktown=i




checktown=t
checked=set()
alltown=set(list(range(1,n+1)))

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]


    checked=checked|{checktown}
    SNOOKcheck=10**16

    for i in (alltown - checked):
        if SNOOKcheck>SNOOK[i]:
            SNOOKcheck=SNOOK[i]
            checktown=i



MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

Buggy python submission (verdict: Time Limit Exceeded):
n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]


checktown=s
checked=set()
alltown=set(list(range(1,n+1)))
checking=set()

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]
            checking=checking|{i[0]}


    checked=checked|{checktown}
    YENcheck=10**16

    for i in (checking - checked):
        if YENcheck>YEN[i]:
            YENcheck=YEN[i]
            checktown=i




checktown=t
checked=set()
alltown=set(list(range(1,n+1)))
checking=set()

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]
            checking=checking|{i[0]}


    checked=checked|{checktown}
    SNOOKcheck=10**16

    for i in (checking - checked):
        if SNOOKcheck>SNOOK[i]:
            SNOOKcheck=SNOOK[i]
            checktown=i



MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

Buggy python submission (verdict: Time Limit Exceeded):
n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]


checktown=s
checked=set()
alltown=set(list(range(1,n+1)))

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]


    checked=checked|{checktown}
    YENcheck=10**16

    for i in (alltown - checked):
        if YENcheck>YEN[i]:
            YENcheck=YEN[i]
            checktown=i




checktown=t
checked=set()
alltown=set(list(range(1,n+1)))

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]


    checked=checked|{checktown}
    SNOOKcheck=10**16

    for i in (alltown - checked):
        if SNOOKcheck>SNOOK[i]:
            SNOOKcheck=SNOOK[i]
            checktown=i



MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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


Fixed submission:
import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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