Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02882 (python)

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

a,b,x = II()

h = (x-a**2*b/2)*2/(a**2)
if h>=0:
    if b-h==0:
        print(0)
    else:
        r = math.degrees(math.atan(a/(b-h)))
        print(90-r)
else:
    z = 2*x/(a*b)
    r = math.degrees(math.atan(z/b))
    print(90-r)

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

a,b,x = II()

h = (x-a**2*b/2)*2/(a**2)
if h>=0:
    r = math.degrees(math.atan(a/(b-h)))
    print(90-r)
else:
    z = 2*x/(a*b)
    r = math.degrees(math.atan(z/b))
    print(90-r)

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from decimal import Decimal

a,b,x = II()

h = Decimal((x-a**2*b/2)*2/(a**2))
if h>=0:
    r = math.degrees(math.atan(a/(b-h)))
    print(90-r)
else:
    z = Decimal(2*x/(a*b))
    r = math.degrees(math.atan(z/b))
    print(90-r)
Problem p02893 (python)

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]
 
N = I()
X = str(input())
Xr = ''.join('1' if c=='0' else '0' for c in X)

ans = 0
divisors = use_divisors(2*N)
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = Xr[:d//2]
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

#時間計測

def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]
 
N = I()
X = str(input())
Xr = ''.join('1' if c=='0' else '0' for c in X)

divisors = use_divisors(2*N)
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = Xr[:d//2]
    Tc = T+Tr
    count = int(T,2)
    if Tc*(N//d)+Tc[:N-d*(N//d)] <= X:
    #    count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

print(ans)
Problem p02920 (python)

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: return self.hq[0].val
        else: return self.hq[0]

N = I()
S = III()

S.sort()
a = [Heapq([],True) for _ in range(N+1)]
count = [0]*(N+1)

s = S.pop()
a[N].push(s)
count[N] = 1

while S:
    flag = False
    temp = S.pop()
    for i in range(1,N+1)[::-1]:
        if count[i]:
            if temp<a[i].top():
                x = a[i].pop()
                count[i] -= 1
                a[i-1].push(x)
                a[i-1].push(temp)
                count[i-1] += 2
                flag = True
                break
    if not flag:
        print('No')
        exit()

print('Yes')

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from heapq import heapify, heappop, heappush, heappushpop,\
                  _heapify_max, _siftdown_max, _siftup_max

def _heappush_max(heap, item):
    heap.append(item)
    _siftdown_max(heap, 0, len(heap)-1)

def _heappop_max(heap):
    lastelt = heap.pop()
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup_max(heap, 0)
        return returnitem
    return lastelt

N = I()
S = III()

S.sort()
A = [[S.pop(),N]]
_heapify_max(A)
while S:
    temp = S.pop()
    a = _heappop_max(A)
    if a[0]<=temp:
        print('No')
        exit()
    else:
        if a[1]>=2:
            _heappush_max(A,[a[0],a[1]-1])
            _heappush_max(A,[temp,a[1]-1])
    
print('Yes')
Problem p02940 (python)

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 998244353

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_left


def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans

N = I()
S = str(input())

r = []
g = []
b = []

m1 = []
m2 = []
m3 = []

for i in range(3*N):
    if S[i]=='R':
        r.append(i)
    elif S[i]=='G':
        g.append(i)
    else:
        b.append(i)

for i in range(N):
    m1.append(min(r[i],g[i],b[i]))
    m2.append(sorted([r[i],g[i],b[i]])[1])
    m3.append(max(r[i],g[i],b[i]))

ans = fact(N)

for i in range(N):
    left = bisect_left(m1,m2[i])
    ans = ans*(left-i)%mod

for i in range(N)[::-1]:
    right = N-bisect_left(m3,m2[i])
    ans = ans*(right-(N-1-i))%mod

print(ans)

Buggy submission (verdict: Runtime Error):
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 998244353

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import statistics
from bisect import bisect_left


def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans

N = I()
S = str(input())

r = []
g = []
b = []

m1 = []
m2 = []
m3 = []

for i in range(3*N):
    if S[i]=='R':
        r.append(i)
    elif S[i]=='G':
        g.append(i)
    else:
        b.append(i)

for i in range(N):
    m1.append(min(r[i],g[i],b[i]))
    m2.append(statistics.median([r[i],g[i],b[i]]))
    m3.append(max(r[i],g[i],b[i]))

ans = fact(N)

for i in range(N):
    left = bisect_left(m1,m2[i])
    ans = ans*(left-i)%mod

for i in range(N)[::-1]:
    right = N-bisect_left(m3,m2[i])
    ans = ans*(right-(N-1-i))%mod

print(ans)
Problem p03006 (python)

Fixed submission:
import sys
from collections import Counter

N=int(input())
if N==1:
  print(1)
  sys.exit()
  
x=[0]*N
y=[0]*N
for i in range(N):
  x[i],y[i] = map(int, input().split())
a = []
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    else:
      a.append(str(x[j]-x[i])+'&'+str(y[j]-y[i]))
    
a=Counter(a)
common = a.most_common(1)[0][1]
print(N-common)

Buggy submission (verdict: Runtime Error):
from collections import Counter
N=int(input())
x=[0]*N
y=[0]*N
for i in range(N):
  x[i],y[i] = map(int, input().split())
a = []
for i in range(N):
  for j in range(i+1,N):
    a.append(str(x[j]-x[i])+'&'+str(y[j]-y[i]))
    
a=Counter(a)
common = a.most_common(1)[0][1]
print(N-common)
Problem p03044 (python)

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N = I()
u,v,w = Line(N-1)

c = [[] for _ in range(N)]
for i in range(N-1):
  c[u[i]-1].append([v[i]-1, w[i]])
  c[v[i]-1].append([u[i]-1, w[i]])

d=[-1]*N
v=0
check_visited = [False]*N
check_visited[v] = True
S = [v]
d[v]=0
while S:
  v1 = S.pop()
  for i in c[v1]:
    if check_visited[i[0]] == False:
      check_visited[i[0]] = True
      d[i[0]] = d[v1] + i[1]
      S.append(i[0])

for i in range(N):
  if d[i]%2==0:
    print('0')
  else:
    print('1')

Buggy submission (verdict: Runtime Error):
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N = I()
u,v,w = Line(N-1)

c = [[float('inf')]*N for _ in range(N)]
for i in range(N-1):
  c[i][i] = 0
  c[u[i]-1][v[i]-1] = w[i]
  c[v[i]-1][u[i]-1] = w[i]

for k in range(N):
  for i in range(N):
    for j in range(N):
      c[i][j]=min(c[i][j],c[i][k]+c[k][j])

from scipy.sparse.csgraph import floyd_warshall
cost=floyd_warshall(c)
print(cost)

for i in range(N):
  if c[i][0]%2==0:
    print('0')
  else:
    print('1')
Problem p03074 (python)

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,K = II()
S = str(input())

num = 0
for i in range(N):
    if i==N-1:
        print(N)
        exit()
    if S[i]=='0' and S[i+1]=='1':
        num += 1
        place = i+1
    if num==K:
        break

if num<K:
    print(N)
    exit()

for i in range(place+1,N):
    if i==N-1 and S[i]=='1':
        print(N)
        exit()
    if S[i]=='0':
        break

place = i-1

ans = place+1

for i in range(1,N):
    if S[i-1]=='0' and S[i]=='1':
        val = N-1
        for j in range(place+2,N):
            val = j
            if j==N-1:
                break
            if S[j]=='1' and S[j+1]=='0':
                break
        if val-i+1>ans:
            ans = val-i+1
        place = val

print(ans)

Buggy submission (verdict: Runtime Error):
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,K = II()
S = str(input())

num = 0
for i in range(N):
    if S[i]=='0' and S[i+1]=='1':
        num += 1
        place = i+1
    if num==K:
        break

if num<K:
    print(N)
    exit()

for i in range(place+1,N):
    if i==N-1 and S[i]=='1':
        print(N)
        exit()
    if S[i]=='0':
        break

place = i-1

ans = place+1

for i in range(1,N):
    if S[i-1]=='0' and S[i]=='1':
        val = N-1
        count = 0
        for j in range(place+2,N):
            val = j
            if S[j]=='1':
                count += 1
            if count==2:
                break
        if val-i+1>ans:
            ans = val-i+1
        place = val

print(ans)
Problem p03078 (python)

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

X,Y,Z,K = II()
A = III()
B = III()
C = III()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

a = []
if X*Y*Z <= 10**6:
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                a.append(A[i]+B[j]+C[k])
    a.sort(reverse=True)
    for i in range(K):
        print(a[i])
else:
    for i in range(X):
        if i==0: jmax = Y
        else: jmax = min(Y,math.ceil(5000/i))
        for j in range(jmax):
            if i*j==0: kmax = Z
            else: kmax = min(Z,math.ceil(5000/i/j))
            for k in range(kmax):
                a.append(A[i]+B[j]+C[k])
    a.sort(reverse=True)   
    for i in range(K):
        print(a[i])

Buggy submission (verdict: Runtime Error):
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

X,Y,Z,K = II()
A = III()
B = III()
C = III()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

a = []
if X*Y*Z <= 10**6:
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                a.append(A[i]+B[j]+C[k])
    a.sort(reverse=True)
    for i in range(K):
        print(a[i])
else:
    for i in range(X):
        for j in range(min(Y,math.ceil(5000/i))):
            for k in range(min(Z,math.ceil(5000/i/j))):
                a.append(A[i]+B[j]+C[k])
    a.sort(reverse=True)   
    for i in range(K):
        print(a[i])
Problem p03267 (python)

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

N = math.floor(math.log2(L))+1
M = 0
edge = []
for i in range(N-1):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(N-1)[::-1]:
    if L-2**i >= 2**(N-1):
        edge.append([i,N-1,L-2**i])
        M += 1
        L -= 2**i

print(N,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

r = math.floor(math.log2(L+1))
M = 0
edge = []
for i in range(r):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(r)[::-1]:
    if L-2**i >= 2**r:
        edge.append([i,r,L-2**i])
        M += 1
        L -= 2**i

print(r+1,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

r = math.floor(math.log2(L+1))
M = 0
edge = []
for i in range(r):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(r)[::-1]:
    if L-2**i >= 2**r:
        edge.append([i,r,L-2**i])
        M += 1
        L -= 2**i

print(r+1,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])
Problem p03305 (python)

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E[u1].items():
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = [dict() for _ in range(n)]
p2 = [dict() for _ in range(n)]
for i in range(m):
  p[u[i]-1][v[i]-1] = a[i]
  p[v[i]-1][u[i]-1] = a[i]
  p2[u[i]-1][v[i]-1] = b[i]
  p2[v[i]-1][u[i]-1] = b[i]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

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

Buggy submission (verdict: Runtime Error):
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

c = []
for i in range(m):
  c.append([u[i]-1,v[i]-1,a[i]])
  c.append([v[i]-1,u[i]-1,a[i]])

from heapq import heappop, heappush
inf=float('inf')
d=[inf for _ in range(n)]
d[s-1]=0
prev=[None]*n
p=dict()
for i,j,k in c: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[s-1],s-1))
while q:
  du, u1 = heappop(q)
  if d[u1]<du: continue
  for v1,weight in p.get(u1,[]):
    alt=du+weight
    if d[v1]>alt:
      d[v1]=alt
      prev[v1]=u1
      heappush(q, (alt,v1))

c2 = []
for i in range(m):
  c2.append([u[i]-1,v[i]-1,b[i]])
  c2.append([v[i]-1,u[i]-1,b[i]])

d2=[inf for _ in range(n)]
d2[t-1]=0
prev=[None]*n
p=dict()
for i,j,k in c2: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d2[t-1],t-1))
while q:
  du, u2 = heappop(q)
  if d2[u2]<du: continue
  for v2,weight in p.get(u2,[]):
    alt=du+weight
    if d2[v2]>alt:
      d2[v2]=alt
      prev[v2]=u2
      heappush(q, (alt,v2))

ans = d[n-1]+d2[n-1]
for i in range(1,n):
  ans.append(min(ans[i-1],d[n-1-i]+d2[n-1-i]))

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