Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
L = len(S)

INF = float('inf')
dp = [[INF]*2 for _ in range(L)]
dp[0][0] = int(S[-1])
dp[0][1] = 10-int(S[-1])
S = S[::-1]
for i,c in enumerate(S[1:]):
    c = int(c)
    d = 10-c
    dp[i+1][0] = min(dp[i+1][0], dp[i][0]+c)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0]+d)
    c += 1
    d -= 1
    if c==10:
        dp[i+1][1] = min(dp[i+1][1], dp[i][1])
    else:
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+c)
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+d)
print(min(dp[-1][0], dp[-1][1]+1))

Fixed submission:
S = input()
L = len(S)

INF = float('inf')
dp = [[INF]*2 for _ in range(L)]
dp[0][0] = int(S[-1])
dp[0][1] = 10-int(S[-1])
S = S[::-1]
for i,c in enumerate(S[1:]):
    c = int(c)
    d = 10-c
    dp[i+1][0] = min(dp[i+1][0], dp[i][0]+c)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0]+d)
    c += 1
    d -= 1
    if c==10:
        dp[i+1][1] = min(dp[i+1][1], dp[i][1])
    else:
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+c)
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+d)
print(min(dp[-1][0], dp[-1][1]+1))
Buggy python submission (verdict: Time Limit Exceeded):
r1,c1,r2,c2 = map(int,input().split())

MOD = 10**9+7
def inv(n):
    return pow(n,MOD-2,MOD)

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(r):
        ret *= (n-i)
        ret *= inv(i+1)
    ret %= MOD
    return ret

ans = 0
a = comb(r1+c1-1, r1)
b = comb(r1+c2, r1)
for r in range(r1,r2+1):
    iv = inv(r+1)
    a *= (r+c1) * iv
    b *= (r+c2+1) * iv
    ans += b-a
ans %= MOD
print(ans)

Fixed submission:
r1,c1,r2,c2 = map(int,input().split())

MOD = 10**9+7
MAXN = 2*10**6+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for r in range(r1,r2+1):
    ans += ncr(r+c2+1, r+1) - ncr(r+c1, r+1)
ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
r1,c1,r2,c2 = map(int,input().split())

MOD = 10**9+7
MAXN = 10**6+5
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(r):
        ret *= (n-i)
        ret *= inv[i+1]
    ret %= MOD
    return ret

ans = 0
a = comb(r1+c1-1, r1)
b = comb(r1+c2, r1)
for r in range(r1,r2+1):
    a *= (r+c1) * inv[r+1]
    b *= (r+c2+1) * inv[r+1]
    ans += b-a
ans %= MOD
print(ans)

Fixed submission:
r1,c1,r2,c2 = map(int,input().split())

MOD = 10**9+7
MAXN = 2*10**6+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for r in range(r1,r2+1):
    ans += ncr(r+c2+1, r+1) - ncr(r+c1, r+1)
ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
k,x = map(int,input().split())
print("Yes" if k*500 >= x "No")

Fixed submission:
k,x = map(int,input().split())
print("Yes" if k*500 >= x else "No")
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = list(map(int,input().split()))
s = set()
B = []
for a in A:
    t = a & -a
    s.add(t)
    if len(s) > 1:
        print(0)
        exit()
    B.append(a // t)

from math import gcd
l = 1
for b in B:
    l = b*l // gcd(b,l)

x = l*t // 2
ans = M//x - M//(2*x)
print(ans)

Fixed submission:
N,M = map(int,input().split())
A = list(map(int,input().split()))
s = set()
B = []
for a in A:
    t = a & -a
    s.add(t)
    if len(s) > 1:
        print(0)
        exit()
    B.append(a // t)

from fractions import gcd
l = 1
for b in B:
    l = b*l // gcd(b,l)

x = l*t // 2
ans = M//x - M//(2*x)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
C = list(map(int,input().split()))
C.sort(reverse=True)
MOD = 10**9+7

ans = 0
d = pow(2,N-2,MOD)
base = pow(2,N-1,MOD)
for i,c in enumerate(C):
    ans += c * (base + i*d)
ans *= pow(2,N,MOD)
ans %= MOD
print(ans)

Fixed submission:
N = int(input())
C = list(map(int,input().split()))
C.sort(reverse=True)
MOD = 10**9+7
if N==1:
    print((C[0]*2)%MOD)
    exit()

ans = 0
d = pow(2,N-2,MOD)
base = pow(2,N-1,MOD)
for i,c in enumerate(C):
    ans += c * (base + i*d)
ans *= pow(2,N,MOD)
ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
xys = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        xys[i].append((x-1,y))

ans = 0
for b in range(1<<N):
    cnt = bin(b).count('1')
    if cnt <= ans: continue
    for i in range(N):
        if b&(1<<i):
        for x,y in xys[i]:
                if y==1 and b&(1<<x): continue
                if y==0 and b&(1<<x)==0: continue
                break
            else:
                continue
            break
    else:
        ans = cnt
print(ans)

Fixed submission:
N = int(input())
xs = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        xs[i].append((x-1,y))
ans = 0
for b in range(1<<N):
    mujun = False
    for k,z in enumerate(xs):
        for x,y in z:
            if b&(1<<k):
                if b&(1<<x):
                    if y==0:
                        mujun = True
                else:
                    if y==1:
                        mujun = True
            if mujun:
                break
        if mujun:
            break
    if not mujun:
        tmp = bin(b).count('1')
        ans = max(ans, tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

arr = [0] * 60
for a in A:
    for i in range(60):
        if a&(1<<i):
            arr[i] += 1

ans = 0
for i,a in enumerate(arr):
    b = N-a
    ans += a*b * 2**i
    ans %= MOD
print(ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

arr = [0] * 60
for a in A:
    for i in range(60):
        if a&(1<<i):
            arr[i] += 1

ans = 0
for i,a in enumerate(arr):
    b = N-a
    ans += a*b * 2**i
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
B = [list(map(int,input().split())) for i in range(H)]

C = [[] for i in range(H)]
for i,(arow,brow) in enumerate(zip(A,B)):
    for a,b in zip(arow,brow):
        d = abs(a-b)
        C[i].append(d)

dp = [set() for i in range(W)]
dp[0].add(0)
for i,crow in enumerate(C):
    dp2 = [set() for j in range(W)]
    for j,(c,dpr) in enumerate(zip(C[i],dp)):
        for d in dpr:
            dp2[j].add(d+c)
            dp2[j].add(d-c)
    for j,c in enumerate(C[i]):
        if j==0: continue
        for d in dp2[j-1]:
            dp2[j].add(d+c)
            dp2[j].add(d-c)
    dp = dp2

print(min(abs(a) for a in dp[-1]))

Fixed submission:
H,W = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
B = [list(map(int,input().split())) for i in range(H)]

C = [[] for i in range(H)]
for i,(arow,brow) in enumerate(zip(A,B)):
    for a,b in zip(arow,brow):
        d = abs(a-b)
        C[i].append(d)

ofs = (H+W)*100
dp = [0] * W
dp[0] = (1<<ofs)
for i,crow in enumerate(C):
    dp2 = [0] * W
    for j,(c,d) in enumerate(zip(C[i],dp)):
        dp2[j] |= (d<<c)
        dp2[j] |= (d>>c)
    for j,c in enumerate(C[i]):
        if j==0: continue
        dp2[j] |= (dp2[j-1]<<c)
        dp2[j] |= (dp2[j-1]>>c)
    dp = dp2

ans = ofs
l = len(bin(dp[-1]))
for i in range(l):
    if dp[-1] & (1<<i):
        ans = min(ans, abs(i-ofs))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
B = [list(map(int,input().split())) for i in range(H)]

C = [[] for i in range(H)]
for i,(arow,brow) in enumerate(zip(A,B)):
    for a,b in zip(arow,brow):
        d = abs(a-b)
        C[i].append(d)

dp = [set() for i in range(W)]
dp[0].add(0)
for i,crow in enumerate(C):
    dp2 = [set() for j in range(W)]
    for j,(c,dpr) in enumerate(zip(C[i],dp)):
        for d in dpr:
            dp2[j].add(d+c)
            dp2[j].add(d-c)
    for j,c in enumerate(C[i]):
        if j==0: continue
        for d in dp2[j-1]:
            dp2[j].add(d+c)
            dp2[j].add(d-c)
    dp = dp2

print(min(abs(a) for a in dp[-1]))

Fixed submission:
H,W = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
B = [list(map(int,input().split())) for i in range(H)]

C = [[] for i in range(H)]
for i,(arow,brow) in enumerate(zip(A,B)):
    for a,b in zip(arow,brow):
        d = abs(a-b)
        C[i].append(d)

ofs = (H+W)*100
dp = [0] * W
dp[0] = (1<<ofs)
for i,crow in enumerate(C):
    dp2 = [0] * W
    for j,(c,d) in enumerate(zip(C[i],dp)):
        dp2[j] |= (d<<c)
        dp2[j] |= (d>>c)
    for j,c in enumerate(C[i]):
        if j==0: continue
        dp2[j] |= (dp2[j-1]<<c)
        dp2[j] |= (dp2[j-1]>>c)
    dp = dp2

ans = ofs
l = len(bin(dp[-1]))
for i in range(l):
    if dp[-1] & (1<<i):
        ans = min(ans, abs(i-ofs))
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
mk = min(K,N+1)
qs = [deque() for i in range(mk)]

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + mk <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)

Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
from collections import defaultdict
qs = defaultdict(lambda: deque())

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + K <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int,input().split()))

cums = [0]
for a in A:
    cums.append(cums[-1] + a)

ans = 0
for d in range(1,min(K,N+1)):
    for i in range(N+1-d):
        v = (cums[i+d] - cums[i]) % K
        if v==d:
            ans += 1
print(ans)

Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
from collections import defaultdict
qs = defaultdict(lambda: deque())

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + K <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int,input().split()))

cums = [0]
for a in A:
    cums.append(cums[-1] + a)

ans = 0
for d in range(1,K):
    for i in range(N+1-d):
        v = (cums[i+d] - cums[i]) % K
        if v==d:
            ans += 1
print(ans)

Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
from collections import defaultdict
qs = defaultdict(lambda: deque())

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + K <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int,input().split()))

cums = [0]
for a in A:
    cums.append(cums[-1] + a)

ans = 0
for d in range(1,K):
    for i in range(N+1-d):
        v = (cums[i+d] - cums[i]) % K
        if v==d:
            ans += 1
print(ans)

Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
from collections import defaultdict
qs = defaultdict(lambda: deque())

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + K <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)
Buggy python submission (verdict: Runtime Error):
X,Y = map(int,input().split())
MOD = 10**9+7

if (X+Y)%3:
    print(0)
    exit()
n = (X+Y)//3
r = X-n
if not 0 <= r <= n:
    print(0)

MAXN = n
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
def comb(n,r):
    ret = 1
    for i in range(r):
        ret *= n-i
        ret *= inv[i+1]
        ret %= MOD
    return ret

print(comb(n,r))

Fixed submission:
X,Y = map(int,input().split())
if X>Y:
    X,Y = Y,X
if(X+Y)%3:
    print(0)
    exit()
n = (X+Y)//3
if X < n:
    print(0)
    exit()

MOD = 10**9+7
r = X-n

maxn = n+5
fac = [1,1] + [0]*maxn
finv = [1,1] + [0]*maxn
inv = [0,1] + [0]*maxn
for i in range(2,maxn+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

print(ncr(n,r))
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
H = [0] + list(map(int,input().split()))

INF = float('inf')
dp = [[INF]*(N-K+1) for _ in range(N+1)]
dp[0][0] = 0

for i,h in enumerate(H):
    if i==0: continue
    for j in range(N-K,0,-1):
        for k in range(i):
            c = max(0, h - H[k])
            dp[i][j] = min(dp[i][j], dp[k][j-1] + c)
print(min(row[-1] for row in dp))

Fixed submission:
N,K = map(int,input().split())
H = [0] + list(map(int,input().split()))

INF = float('inf')
dp = [[INF]*(N-K+1) for _ in range(N+1)]
dp[0][0] = 0

for i,h in enumerate(H):
    if i==0: continue
    for j in range(N-K,0,-1):
        for k in range(i):
            c = max(0, h - H[k])
            dp[i][j] = min(dp[i][j], dp[k][j-1] + c)
print(min(row[-1] for row in dp))
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

def is_ok(m):
    c = 0
    for a,f in zip(A,F):
        d = m//f
        c += max(0, a-d)
        if c > K:
            return False
    return True

ok = 10**13
ng = -1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
F = list(map(int,input().split()))
F.sort(reverse=True)

sa = sum(A)
if K >= sa:
    print(0)
    exit()

def isok(b):
    k = 0
    for a,f in zip(A,F):
        if a > b//f:
            k += a-(b//f)
            if k > K:
                return False
    return True

ok = 10**12+1
ng = 0

while ok-ng > 1:
    m = (ok+ng)//2
    if isok(m):
        ok = m
    else:
        ng = m
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
F = list(map(int,input().split()))
F.sort(reverse=True)

sa = sum(A)
if K >= sa:
    print(0)
    exit()

def isok(b):
    k = 0
    for a,f in zip(A,F):
        if a > b//f:
            k += a-(b//f)
            if k > K:
                return False
    return True

ok = 10**12+1
ng = 0

while ok-ng > 1:
    m = (ok+ng)//2
    if isok(m):
        ok = m
    else:
        ng = m
print(ok)

Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
F = list(map(int,input().split()))
F.sort(reverse=True)

sa = sum(A)
if K >= sa:
    print(0)
    exit()

def isok(b):
    k = 0
    for a,f in zip(A,F):
        if a > b//f:
            k += a-(b//f)
            if k > K:
                return False
    return True

ok = 10**12+1
ng = 0

while ok-ng > 1:
    m = (ok+ng)//2
    if isok(m):
        ok = m
    else:
        ng = m
print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

N = int(input())
S = [input() for i in range(N)]

es = [[] for i in range(N)]
for i,row in enumerate(S):
    for j,c in enumerate(row):
        if c=='1':
            es[i].append(j)
            es[j].append(i)

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

if not is_bipartite():
    print(-1)
    exit()

INF = float('inf')
dists = [[1 if c=='1' else INF for c in row] for row in S]
for i in range(N):
    dists[i][i] = 0

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

print(max(max(row) for row in dists) + 1)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N = int(input())
S = [input() for i in range(N)]

es = [[] for i in range(N)]
for i,row in enumerate(S):
    for j,c in enumerate(row):
        if c=='1':
            es[i].append(j)
            es[j].append(i)

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

if not is_bipartite():
    print(-1)
    exit()

INF = float('inf')
dists = [[1 if c=='1' else INF for c in row] for row in S]
for i in range(N):
    dists[i][i] = 0

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

print(max(max(row) for row in dists) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)

from collections import deque
mindist = N
opt = None
for g,tos in enumerate(es):
    for s in tos:
        q = deque([(s,0)])
        prev = [-1]*N
        while q:
            v,d = q.popleft()
            for to in es[v]:
                if to==g: break
                if prev[to] >= 0: continue
                prev[to] = v
                q.append((to,d+1))
            else:
                continue
            break
        else:
            continue
        if d+1 >= mindist: continue
        mindist = d+1
        opt = [g,v]
        while prev[opt[-1]] >= 0:
            opt.append(prev[opt[-1]])
if opt:
    ans = [o+1 for o in opt]
    print(len(ans))
    print(*ans, sep='\n')
else:
    print(-1)

Fixed submission:
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)

from collections import deque
tmpdist = N
ans = None
for to in range(N):
    for fr in es[to]:
        dist = [N] * N
        dist[fr] = 0
        prev = [-1] * N
        q = deque([fr])
        while q:
            v = q.popleft()
            if v==to: break
            for w in es[v]:
                if dist[w] < N: continue
                if v==to and w==fr: continue
                dist[w] = dist[v] + 1
                prev[w] = v
                q.append(w)
        else:
            continue
        if dist[to] < tmpdist:
            tmpdist = dist[to]
            ans = set()
            v = to
            while 1:
                ans.add(v+1)
                if prev[v] < 0: break
                v = prev[v]
if ans is None:
    print(-1)
else:
    print(len(ans))
    print(*ans, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
N,M,P = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

g = [[] for i in range(N)]
revg = [[] for i in range(N)]

for a,b,_ in ABC:
    a,b = a-1, b-1
    g[a].append(b)
    revg[b].append(a)

st = set([0])
stack = [0]
while stack:
    v = stack.pop()
    for to in g[v]:
        if to in st: continue
        st.add(to)
        stack.append(to)

revst = set([N-1])
stack = [N-1]
while stack:
    v = stack.pop()
    for to in revg[v]:
        if to in revst: continue
        revst.add(to)
        stack.append(to)

use = st & revst
es = []
for a,b,c in ABC:
    a,b = a-1, b-1
    if a in use and b in use:
        es.append((a,b,c))

INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
    for fr,to,c in es:
        cost = -(c-P)
        if d[to] > d[fr]+cost:
            d[to] = d[fr] + cost
            if i == N-1:
                print(-1)
                exit()

print(max(0,-d[-1]))

Fixed submission:
N,M,P = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

g = [[] for i in range(N)]
revg = [[] for i in range(N)]

for a,b,_ in ABC:
    a,b = a-1, b-1
    g[a].append(b)
    revg[b].append(a)

st = set([0])
stack = [0]
while stack:
    v = stack.pop()
    for to in g[v]:
        if to in st: continue
        st.add(to)
        stack.append(to)

revst = set([N-1])
stack = [N-1]
while stack:
    v = stack.pop()
    for to in revg[v]:
        if to in revst: continue
        revst.add(to)
        stack.append(to)

use = st & revst
es = []
for a,b,c in ABC:
    a,b = a-1, b-1
    if a in use and b in use:
        es.append((a,b,c))

INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
    for fr,to,c in es:
        cost = -(c-P)
        if d[to] > d[fr]+cost:
            d[to] = d[fr] + cost
            if i == N-1:
                print(-1)
                exit()

print(max(0,-d[-1]))