Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit
# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))
    xs = sum(a) // 2
    res = [0] * n

    for i in range(n):
        sub = 0
        for j in range(n // 2):
            sub += a[(i + 1 + j * 2) % n]
        res[i] = 2 * (xs - sub)

    print(*res)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit
# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))
    res = [0] * n
    xs = sum(a)
    res[0] = xs - 2 * (sum(a[1::2]))

    for i in range(1, n):
        res[i] = 2 * a[(i - 1) % n] - res[(i - 1) % n]

    print(*res)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))

    b = k
    r = n - k

    @jit(nopython=True)
    def comb():
        com = [[0] * 2005 for _ in range(2005)]
        com[0][0] = 1
        for i in range(1, 2005):
            com[i][0] = 1
            for j in range(1, 2005):
                com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % MOD
        return com

    com = comb()

    for i in range(1, k + 1):
        res = com[r + 1][i] * com[b - 1][i - 1]
        res %= MOD
        print(res)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))

    b = k
    r = n - k

    def comb():
        com = [[0] * 2005 for _ in range(2005)]
        com[0][0] = 1
        for i in range(1, 2005):
            com[i][0] = 1
            for j in range(1, 2005):
                com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % MOD
        return com

    com = comb()

    for i in range(1, k + 1):
        res = com[r + 1][i] * com[b - 1][i - 1]
        res %= MOD
        print(res)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import numpy as np
    l, a, b, m = list(map(int, readline().split()))
    d_min = len(str(a))
    d_max = len(str(a + (l - 1) * b))
    count_d = [-1] * 19

    prev = -1
    for i in range(d_min, d_max + 1):
        power = 10 ** i
        ok = 0
        ng = l + 1
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            x = a + mid * b
            if x < power:
                ok = mid
            else:
                ng = mid
        ok = min(ok, l - 1)
        count_d[i] = ok - prev
        prev = ok

    res = np.array([0, a, 1], dtype="int64")

    for i in range(19):
        count = count_d[i]
        if count == -1:
            continue
        mat = np.array([[10 ** i, 0, 0],
                        [1, 1, 0],
                        [0, b, 1]], dtype="int64")
        mat = np.mod(mat,m)
        cur = np.eye(3, dtype="int64")
        count_bit = format(count, "b")
        for bit in count_bit[::-1]:
            if bit == "1":
                cur = cur @ mat
                cur = np.mod(cur, m)
            mat = mat @ mat
            mat = np.mod(mat, m)
        res = res @ cur
        res = np.mod(res, m)

    print(res[0])


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import numpy as np
    l, a, b, m = list(map(int, readline().split()))
    d_min = len(str(a))
    d_max = len(str(a + (l - 1) * b))
    count_d = [-1] * 19

    prev = -1
    for i in range(d_min, d_max + 1):
        power = 10 ** i
        ok = 0
        ng = l + 1
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            x = a + mid * b
            if x < power:
                ok = mid
            else:
                ng = mid
        ok = min(ok, l - 1)
        count_d[i] = ok - prev
        prev = ok

    res = np.array([0, a, 1], dtype="int64")
    res = np.mod(res, m)

    for i in range(19):
        count = count_d[i]
        if count == -1:
            continue
        mat = np.array([[10 ** i, 0, 0],
                        [1, 1, 0],
                        [0, b, 1]], dtype="int64")
        mat = np.mod(mat, m)
        cur = np.eye(3, dtype="int64")
        count_bit = format(count, "b")
        for bit in count_bit[::-1]:
            if bit == "1":
                cur = np.dot(cur, mat)
                cur = np.mod(cur, m)
            mat = np.dot(mat, mat)
            mat = np.mod(mat, m)
        res = np.dot(res, cur)
        res = np.mod(res, m)

    print(res[0])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def comb_mod(n, r):
    res = 1
    r = min(n - r, r)

    for i in range(r):
        res *= (n - i)
        res %= MOD
        res *= pow((r - i), -1, MOD)

    return res


def main():
    n, m, k = list(map(int, readline().split()))

    com = comb_mod(n * m - 2, k - 2)
    x = 0
    y = 0

    for i in range(n):
        right = n - 1 - i
        x += (right + 1) * right // 2
        x %= MOD

    for i in range(m):
        down = m - 1 - i
        y += (down + 1) * down // 2
        y %= MOD

    ans = 0
    ans += m ** 2 * x * com
    ans += n ** 2 * y * com
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def comb_mod(n, r):
    res = 1
    r = min(n - r, r)

    for i in range(r):
        res *= (n - i)
        res %= MOD
        res *= pow((r - i), MOD - 2, MOD)

    return res


def main():
    n, m, k = list(map(int, readline().split()))

    com = comb_mod(n * m - 2, k - 2)
    x = 0
    y = 0

    for i in range(n):
        right = n - 1 - i
        x += (right + 1) * right // 2
        x %= MOD

    for i in range(m):
        down = m - 1 - i
        y += (down + 1) * down // 2
        y %= MOD

    ans = 0
    ans += m ** 2 * x * com
    ans += n ** 2 * y * com
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    h = list(map(int,ipti().split()))
    dp = [INF] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(1, k+1):
            if i - j >= 0:
                temp = abs(h[i] - h[i-j]) + dp[i-j]
                dp[i] = min(dp[i], temp)

    print(dp[n-1])

if __name__ == '__main__':
    main()

Fixed submission:
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    h = list(map(int,ipti().split()))
    dp = [INF] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(1, k+1):
            if i - j >= 0:
                temp = abs(h[i] - h[i-j]) + dp[i-j]
                dp[i] = min(dp[i], temp)

    print(dp[n-1])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    def chmin(idx):
        mn = INF
        for i in range(1, k+1):
            if idx - i >= 0:
                temp = abs(h[idx] - h[idx-i]) + dp[idx-i]
                if temp < mn:
                    mn = temp
        return mn

    n, k = list(map(int,ipti().split()))
    h = list(map(int,ipti().split()))
    dp = [0] * n

    for i in range(1, n):
        dp[i] = chmin(i)

    print(dp[n-1])

if __name__ == '__main__':
    main()

Fixed submission:
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    h = list(map(int,ipti().split()))
    dp = [INF] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(1, k+1):
            if i - j >= 0:
                temp = abs(h[i] - h[i-j]) + dp[i-j]
                dp[i] = min(dp[i], temp)

    print(dp[n-1])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, a, b, k = list(map(int, readline().split()))
    M = 998244353

    h = (n + 1) // 2
    l = h + 1
    com = [0] * l
    com[0] = 1

    for i in range(1, l):
        t = com[i - 1] * (n + 1 - i)
        t *= pow(i, M - 2, M)
        t %= M
        com[i] = t

    ans = 0
    rng = min(k // a + 1, n)

    for x in range(rng):
        res = k - a * x
        if res % b == 0:
            y = res // b
            if x > h:
                x = n - x
            if y > h:
                y = n - y

            add = com[x] * com[y]
            ans += add
            ans %= M

    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, a, b, k = list(map(int, readline().split()))
    M = 998244353

    h = (n + 1) // 2
    l = h + 1
    com = [0] * l
    com[0] = 1

    for i in range(1, l):
        t = com[i - 1] * (n + 1 - i)
        t *= pow(i, M - 2, M)
        t %= M
        com[i] = t

    ans = 0
    rng = min(k // a + 1, n + 1)

    for x in range(rng):
        res = k - a * x
        if res % b == 0:
            y = res // b
            if y > n:
                continue
            if x > h:
                x = n - x
            if y > h:
                y = n - y
            add = com[x] * com[y]
            ans += add
            ans %= M

    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, c = list(map(int, readline().split()))

    x = [0] * (n + 1)
    v = [0] * (n + 1)

    for i in range(1, n + 1):
        x[i], v[i] = map(int, readline().split())

    right_cum = [0] * (n + 1)
    left_cum = [0] * (n + 1)

    for i in range(1, n + 1):
        right_cum[i] = right_cum[i - 1] + v[i]
        left_cum[i] = left_cum[i - 1] + v[n - i + 1]

    right_nutritive = [0] * (n + 1)
    left_nutritive = [0] * (n + 1)
    right_max_cum = [0] * (n + 1)
    left_max_cum = [0] * (n + 1)

    for i in range(1, n + 1):
        right_nutritive[i] = right_cum[i] - x[i]
        left_nutritive[i] = left_cum[i] - (c - x[n - i + 1])
        right_max_cum[i] = max(right_max_cum[i - 1], right_nutritive[i])
        left_max_cum[i] = max(left_max_cum[i - 1], left_nutritive[i])

    ans = max(*right_nutritive, *left_nutritive)

    for i in range(1, n + 1):
        rl = right_nutritive[i] - x[i] + left_max_cum[n - i]
        lr = left_nutritive[i] - (c - x[n - i + 1]) + right_max_cum[n - i]
        ans = max(ans, rl, lr)

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, c = list(map(int, readline().split()))

    x = [0] * (n + 1)
    v = [0] * (n + 1)

    for i in range(1, n + 1):
        x[i], v[i] = map(int, readline().split())

    right_cum = [0] * (n + 1)
    left_cum = [0] * (n + 1)

    for i in range(1, n + 1):
        right_cum[i] = right_cum[i - 1] + v[i]
        left_cum[i] = left_cum[i - 1] + v[n - i + 1]

    right_nutritive = [0] * (n + 1)
    left_nutritive = [0] * (n + 1)
    right_max_cum = [0] * (n + 1)
    left_max_cum = [0] * (n + 1)

    for i in range(1, n + 1):
        right_nutritive[i] = right_cum[i] - x[i]
        left_nutritive[i] = left_cum[i] - (c - x[n - i + 1])
        right_max_cum[i] = max(right_max_cum[i - 1], right_nutritive[i])
        left_max_cum[i] = max(left_max_cum[i - 1], left_nutritive[i])

    r_temp = max(right_nutritive)
    l_temp = max(left_nutritive)
    ans = max(r_temp, l_temp)

    for i in range(1, n + 1):
        rl = right_nutritive[i] - x[i] + left_max_cum[n - i]
        lr = left_nutritive[i] - (c - x[n - i + 1]) + right_max_cum[n - i]
        ans = max(ans, rl, lr)

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def query(x):
        print(x)
        ret = input()
        if ret == "Vacant":
            sys.exit()
        return ret

    n = int(readline())

    l = 0
    r = n - 1

    ls = query(l)
    rs = query(r)

    while r - l > 1:
        mid = (l + r) // 2
        ms = query(mid)
        if (mid - l) % 2 == 0:
            if ls == ms:
                l = mid + 1
                ls = ms
            else:
                r = mid - 1
                rs = ms
        else:
            if ls == ms:
                r = mid - 1
                rs = ms
            else:
                l = mid + 1
                ls = ms
    query(l)
    query(r)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def query(x):
        print(x)
        ret = input()
        if ret == "Vacant":
            sys.exit()
        return ret

    n = int(readline())

    l = 0
    r = n - 1

    op = {"Male": "Female", "Female": "Male"}

    ls = query(l)
    rs = query(r)

    while r - l > 1:
        mid = (l + r) // 2
        ms = query(mid)
        if (mid - l) % 2 == 0:
            if ls == ms:
                l = mid + 1
                ls = op[ms]
            else:
                r = mid - 1
                rs = op[ms]
        else:
            if ls == ms:
                r = mid - 1
                rs = op[ms]
            else:
                l = mid + 1
                ls = op[ms]
    query(l)
    query(r)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def dfs(u, cost):
        visited[u] = True
        for v, w in edge[u]:
            if costs.get(v) and costs[v] != cost + w:
                print("No")
                sys.exit()
            costs[v] = cost + w
            dfs(v, cost + w)

    from collections import defaultdict
    n, m = map(int, readline().split())
    edge = defaultdict(list)

    for _ in range(m):
        l, r, d = map(int, readline().split())
        edge[l].append((r, d))

    visited = [False] * (n + 1)

    for u in range(1, n + 1):
        costs = dict()
        if not visited[u]:
            dfs(u, 0)
    print("Yes")


if __name__ == '__main__':
    main()


Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)

    for _ in range(m):
        l, r, d = map(int, readline().split())
        edge[l].append((r, d))
        edge[r].append((l, -d))

    visited = [False] * (n + 1)

    for x in range(1, n + 1):
        costs = dict()
        if not visited[x]:
            costs[x] = 0
            que = deque()
            que.append((x, 0))
            while que:
                u, cost = que.popleft()
                visited[u] = True
                while edge[u]:
                    v, w = edge[u].pop()
                    if v in costs:
                        if costs[v] != cost + w:
                            print("No")
                            sys.exit()
                    costs[v] = cost + w
                    que.append((v, cost + w))

    print("Yes")


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    import networkx as nx
    h, w = map(int, readline().split())
    G = nx.DiGraph()

    for i in range(10):
        costs = list(map(int, readline().split()))
        for j, cost in enumerate(costs):
            if i != j:
                G.add_edge(i, j, weight=cost)

    d = nx.algorithms.floyd_warshall(G)

    counter = Counter()
    for _ in range(h):
        nums = list(map(int, readline().split()))
        counter.update(nums)
    ans = 0
    for num in range(10):
        ans += counter[num] * d[num][1]

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    import networkx as nx
    h, w = map(int, readline().split())
    G = nx.DiGraph()

    for i in range(10):
        costs = list(map(int, readline().split()))
        for j, cost in enumerate(costs):
            if i != j:
                G.add_edge(i, j, weight=cost)

    d = nx.algorithms.floyd_warshall(G)

    counter = Counter()
    for _ in range(h):
        nums = list(map(int, readline().split()))
        counter.update(nums)
    ans = 0
    for num in range(10):
        ans += counter[num] * d[num][1]

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from fractions import Fraction
    n = int(readline())
    k = Fraction(4, n)
    kd = k - Fraction(1, 3500)

    for a in range(1, 3501):
        p = Fraction(1, a)
        for b in range(a, 3501):
            q = Fraction(1, b)
            x = p + q
            if x > kd:
                break
            ok = 3500
            ng = 0
            while abs(ng - ok) > 1:
                mid = (ok + ng) // 2
                y = x + Fraction(1, mid)
                if y > k:
                    ng = mid
                else:
                    ok = mid
            if x + Fraction(1, ok) == k:
                return print(a, b, ok)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())

    for a in range(1, 3501):
        for b in range(1, 3501):
            nu = n * a * b
            dn = 4 * a * b - n * (a + b)
            if dn > 0 and nu % dn == 0:
                return print(a, b, nu // dn)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    n = int(readline())
    dist = [[INF] * n for _ in range(n)]
    hq = []
    table = [[0] * n for _ in range(n)]

    for i in range(n):
        a = list(map(int, readline().split()))
        for j in range(i + 1, n):
            hq.append((a[j], i, j))
            table[i][j] = a[j]

    for i in range(n):
        dist[i][i] = 0

    heapq.heapify(hq)
    ans = 0
    while hq:
        cost, u, v = heapq.heappop(hq)
        cur = dist[u][v]
        if cur > cost:
            ans += cost
            dist[u][v] = cost
            for i in range(n):
                dist[i][v] = min(dist[i][v], dist[i][u] + cost)
                dist[i][u] = min(dist[i][u], dist[i][v] + cost)
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][u] + dist[u][j], dist[i][v] + dist[v][j])

    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] != table[i][j]:
                print(-1)
                sys.exit()

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    n = int(readline())
    dist = [[INF] * n for _ in range(n)]
    hq = []
    table = [[0] * n for _ in range(n)]

    for i in range(n):
        a = list(map(int, readline().split()))
        for j in range(i + 1, n):
            hq.append((a[j], i, j))
            table[i][j] = a[j]
            dist[i][j] = a[j]
            dist[j][i] = a[j]

    for i in range(n):
        dist[i][i] = 0

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    dist[j][i] = dist[i][j]

    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] != table[i][j]:
                print(-1)
                sys.exit()

    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(n):
                if k != i and k!= j:
                    if dist[i][j] == dist[i][k] + dist[k][j]:
                        break
            else:
                ans += dist[i][j]

    print(ans)


if __name__ == '__main__':
    main()