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

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(W, H, x, y):
    if W/2 == x and H/2 == y:
        return (W*H)/2, 1

    return (W*H)/2, 0


def main():
    W, H, x, y = read_int_n()
    print('%f %d' % slv(W, H, x, y))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(W, H, x, y):
    if W/2 == x and H/2 == y:
        return (W*H)/2, 1

    if y == H/W * x:
        return (W*H)/2, 0

    ans = max(min((W-x) * H, x*H), min(W * (H-y), W*y))
    if x == 0:
        ans = max(min((W * y) / 2, W * (H-y) / 2))
    if y == 0:
        ans = max(min((x * H) / 2, (W-x) * H / 2))
    return ans, 0


def main():
    W, H, x, y = read_int_n()
    print('%f %d' % slv(W, H, x, y))


if __name__ == '__main__':
    main()
Problem p03006 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    c = defaultdict(list)
    for i in range(N):
        x, y = XY[i]
        for j in range(N):
            if i == j:
                continue
            a, b = XY[j]
            c[(x-a, y-b)].append((i, j))

    ans = 0
    for _, v in c.items():
        l = set()
        r = set()

        for x, y in v:
            l.add(x)
            r.add(y)

        g = (len(l) - len(l & r))
        ans = max(ans, len(l | r) - g)
        # print(v, len(l | r), g, l & r)
    return N - ans


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    c = Counter()
    for i in range(N):
        x, y = XY[i]
        for j in range(N):
            if i == j:
                continue
            a, b = XY[j]
            c[(x-a, y-b)] += 1

    return N - c.most_common(1)[0][1]


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()
Problem p03046 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(M, K):
    if M == 0:
        if K == 0:
            print(0, 0)
        else:
            print(-1)
    elif M == 1:
        if K == 0:
            print(0, 0, 1, 1)
        else:
            print(-1)
    else:
        if K < 2**M:

            for i in range(2**M):
                if i == K:
                    continue
                print(i, '', end='')
            print(K, '', end='')

            for i in range(2**M-1, -1, -1):
                if i == K:
                    continue
                print(i, '', end='')
            print(K, '', end='')

        else:
            print(-1)


def main():
    M, K = read_int_n()
    (slv(M, K))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(M, K):
    if K != 0:
        print(-1)
        return

    for i in range(2**(M-1)+1):
        print(i, i, '', end='')
    return


def main():
    M, K = read_int_n()
    (slv(M, K))


if __name__ == '__main__':
    main()
Problem p03061 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

from fractions import gcd

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, A):
    L = [A[0]]
  
    for a in A[1:]:
        L.append(gcd(L[-1], a))
        
    R = [-1] * N
    R[-1] = A[-1]
    for i in range(N-2, -1, -1):
        R[i] = gcd(R[i+1], A[i])
    
    ans = 0
    for i in range(N):
        if i == 0:
            ans = max(ans, R[i+1])
        elif i == N-1:
            ans = max(ans, L[i-1])
        else:
            ans = max(ans, gcd(L[i-1], R[i+1]))
    return ans
    


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, A):
  
    ans = 0
    for i in range(N):
        cand = A[0] if i != 0 else A[1]
        for j, a in enumerate(A):
            if i == j:
                continue
            cand = math.gcd(cand, a)
            if cand <= ans:
                break
        ans = max(ans, cand)
        
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N  = 10**5
    # A = [10**9] * N
    # print(slv(N, A))


if __name__ == '__main__':
    main()
Problem p03085 (python)

Fixed submission:
b = input().strip()
if b == 'A':
  print('T')
if b == 'T':
  print('A')
if b == 'G':
  print('C')
if b == 'C':
  print('G')

Buggy submission (verdict: Runtime Error):
b = input().strip()
if b == 'A':
  pirnt('T')
if b == 'T':
  print('A')
if b == 'G':
  print('C')
if b == 'C':
  print('G')
Problem p03129 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K):
    return 'YES' if int(math.ceil(N/2)) >= K else 'NO'


def main():
    # N = read_int()
    N, K = read_int_n()
    # A = [read_int_n() for _ in range(N)]
    print(slv(N, K))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def error_mat_print(m):
    for r in m:
        print(r, file=sys.stderr)

def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L, A):

    dp = [[sys.maxsize] * (L+1) for _ in range(5)]
    dp[0][0] = 0

    for i, a in enumerate(A):
        t = dp[0][i]
        dp[0][i+1] = t + a
        t = min(t, dp[1][i])
        dp[1][i+1] = t+ ((a%2) if a != 0 else 2)
        t = min(t, dp[2][i])
        dp[2][i+1] = t + ((a+1)%2)
        t = min(t, dp[3][i])
        dp[3][i+1] =t + ((a%2) if a != 0 else 2)
        t = min(t, dp[4][i])
        dp[4][i+1] = t + a


    return min([dp[i][L] for i in range(5)])

def main():
    L = read_int()
    A = [read_int() for _ in range(L)]
    print(slv(L, A))


if __name__ == '__main__':
    main()
Problem p03145 (python)

Fixed submission:
x, y, z = map(int, input().split())
print(x*y//2)

Buggy submission (verdict: Runtime Error):
x, y, z = map(int, intput().split())
print(x*y//2)
Problem p03165 (python)

Fixed submission:
S = input().strip()
T = input().strip()


dp = [[0] * (len(T)+1) for _ in range(len(S)+1)]

for i, s in enumerate(S):
  for j, t in enumerate(T):
    if s == t:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i][j-1], dp[i-1][j])
ans = []
s = (len(S)-1, len(T)-1)
while True:
  x, y = s
  if x < 0 or y < 0:
    break
  if S[x] == T[y]:
    ans.append(S[x])
    s = (x-1, y-1)
  else:
    if dp[x-1][y] > dp[x][y-1]:
      s = (x-1, y)
    else:
      s = (x, y-1)

    
print(''.join(reversed(ans)))

Buggy submission (verdict: Runtime Error):
S = input().strip()
T = input().strip()


dp = [[0] * (len(T)+1) for _ in range(len(S))]

for i, s in enumerate(S):
  for j, t in enumerate(T):
    if s == t:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i][j-1], dp[i-1][j])
ans = []
s = (len(S)-1, len(T)-1)
while True:
  x, y = s
  if x < 0 or y < 0:
    assert x == y
    break
  if S[x] == T[y]:
    ans.append(S[x])
    s = (x-1, y-1)
  else:
    if dp[x-1][y] > dp[x][y-1]:
      s = (x-1, y)
    else:
      s = (x, y-1)

    
print(''.join(reversed(ans)))
Problem p03171 (python)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
#import random
#N = 3000
#A = [random.randint(1, 10**9) for _ in range(N)]


dp = [[0] * (N+1) for _ in range(N+1)]
for g in range(N):
  for l in range(N-g):
    r = l + g
    n = r - l
    s = -1 if (N-n) % 2 == 0 else 1
    lv = dp[l+1][r] + s*A[l]
    rv = dp[l][r-1] + s*A[r]
    if s*lv > s*rv:
      dp[l][r] = lv
    else:
      dp[l][r] = rv

print(dp[0][N-1])

Buggy submission (verdict: Runtime Error):
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

#import random
#N = 400
#A = [random.randint(1, 10**9) for _ in range(N)]
INF = 1.0e+100

@lru_cache(maxsize=None)
def f(l, r, xy):
  if l > r:
    return xy
  
  n = r - l
  if (N - n) % 2 == 0:
    s = -1
  else:
    s = 1
    
  lv = f(l+1, r, xy + s*A[l])
  rv = f(l, r-1, xy + s*A[r])
  
  if s*lv > s*rv:
    return lv
  else:
    return rv
    
   
print(f(0, N-1, 0))
Problem p03173 (python)

Fixed submission:
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

INF = 1.0e+100


dp = [[[None, INF] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N):
    dp[i][i+1] = [A[i], 0]

for g in range(2, N+1):
    for l in range(N-g+1):
        r = l + g
        for i in range(l+1, r):
            lv, lc = dp[l][i]
            rv, rc = dp[i][r]
            nc = lv + rv + lc + rc
            if dp[l][r][1] > nc:
                dp[l][r][0] = lv + rv
                dp[l][r][1] = nc

print(dp[0][N][1])

Buggy submission (verdict: Runtime Error):
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))
INF = 1.0e+100

@lru_cache(maxsize=None)
def f(l, r):
  if r - l == 1:
    return (A[l], 0)
  ret = (INF, INF)
  for i in range(l+1, r):
    (lr, lc) = f(l, i)
    (rr, rc) = f(i, r)
    if lr+rr+lc+rc < ret[1]:
      ret = (lr+rr, lr+rr+lc+rc)
  return ret

print(f(0, N)[1])

Buggy submission (verdict: Runtime Error):
from functool import lru_cache
N = int(input())
A = list(map(int, input().split()))
INF = 1.0e+100

@lru_cache(maxsize=None)
def f(l, r):
  if r - l == 1:
    return (A[l], 0)
  ret = (INF, INF)
  for i in range(l+1, r):
    (lr, lc) = f(l, i)
    (rr, rc) = f(i, r)
    if lr+rr+lc+rc < ret[1]:
      ret = (lr+rr, lr+rr+lc+rc)
  return ret

print(f(0, N)[1])

Buggy submission (verdict: Runtime Error):
N = input()
A = list(map(int, input().split()))
INF = 1.0e+100

def f(l, r):
  if r - l == 1:
    return A[l]
  ret = INF
  for i in range(l+1, r):
    lr = f(l, i)
    rr = f(i, r)
    ret = min(ret, lr+rr)
  return ret

print(f(l,r))
Problem p03175 (python)

Fixed submission:

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = [set() for _ in range(N+1)]

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)

Buggy submission (verdict: Runtime Error):

from collections import defaultdict

N = int(input())
g = defaultdict(set)

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)
Problem p03206 (python)

Fixed submission:
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join(a))

Buggy submission (verdict: Runtime Error):
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join())

Buggy submission (verdict: Runtime Error):
d = int(input())
a=['Christmas']
for i in range(25-d):
  a.append('Eve')
print(' '.join

Buggy submission (verdict: Runtime Error):
d = int(input())
a=［'Christmas'］
for i in ranage(25-d):
  a.append('Eve')
print(' '.join(a))
Problem p03305 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(n, m, s, t, UVAB):
    g = defaultdict(list)
    for u, v, a, b in UVAB:
        g[u].append((v, (a, b)))
        g[v].append((u, (a, b)))

    def d(s, ck):
        dist = [0 if s == i else sys.maxsize for i in range(n+1)]
        # p = [None for i in range(n+1)]
        q =[]
        heapq.heappush(q, (dist[s], s))
        while q:
            c, u = heapq.heappop(q)
            if dist[u] > c:
                continue
            for v, cost in g[u]:
                alt = dist[u] + cost[ck]
                if dist[v] > alt:
                    dist[v] = alt
                    heapq.heappush(q, (alt, v))
        return dist

    dist0 = d(s, 0)
    dist1 = d(t, 1)

    ans = [sys.maxsize] * (n+1)
    
    for i in range(n-1, -1, -1):
        # print(i)
        ans[i] = min(ans[i+1], dist1[i+1] + dist0[i+1])
    c = 10**15
    return '\n'.join(map(lambda x: str(c-x), ans[:-1]))


def main():
    n, m, s, t = read_int_n()
    UVAB = [read_int_n() for _ in range(m)]

    
    print(slv(n, m, s, t, UVAB))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import heapq
 
def dijkstra(s, G):
    que = [(0, s)]
    d = [float("inf")]*len(G)
    d[s] = 0
    while que:
        c, v = heapq.heappop(que)
        if d[v] > c: continue
        for to, cost in G[v]:
            if d[to] > d[v] + cost:
                d[to] = d[v] + cost
                heapq.heappush(que, (d[to], to))
    return d
 
n, m, s, t = map(int, raw_input().split())
s, t = s - 1, t - 1 
G0, G1 = [[] for i in xrange(n)], [[] for i in xrange(n)]
for i in range(m):
    ui, vi, ai, bi = map(int, raw_input().split())
    ui, vi = ui - 1, vi - 1
    G0[ui].append((vi, ai))
    G0[vi].append((ui, ai))
    G1[ui].append((vi, bi))
    G1[vi].append((ui, bi))
 
d0 = dijkstra(s, G0)
d1 = dijkstra(t, G1)
 
yen = 10**15
ans = [float("inf")]*(n + 1)
for i in xrange(n - 1, -1, -1):
    ans[i] = min(ans[i + 1], d0[i] + d1[i])
 
for i in xrange(n):
    print yen - ans[i]