Problem:


Score : 1200 points

Problem Statement

We have N boxes numbered 1 to N, and M balls numbered 1 to M.
Currently, Ball i is in Box A_i.

You can do the following operation:

Choose a box containing two or more balls, pick up one of the balls from that box, and put it into another box.

Since the balls are very easy to break, you cannot move Ball i more than C_i times in total.
Within this limit, you can do the operation any number of times.

Your objective is to have Ball i in Box B_i for every i (1 \leq i \leq M).
Determine whether this objective is achievable.
If it is, also find the minimum number of operations required to achieve it.

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq A_i,B_i \leq N

1 \leq C_i \leq 10^5

In the situation where the objective is achieved, every box contains one or more balls.
That is, for every i (1 \leq i \leq N), there exists j such that B_j=i.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

If the objective is unachievable, print -1; if it is achievable, print the minimum number of operations required to achieve it.

Sample Input 1

3 3
1 2 1
2 1 1
1 3 2

Sample Output 1

3

We can achieve the objective in three operations, as follows:

Pick up Ball 1 from Box 1 and put it into Box 2.

Pick up Ball 2 from Box 2 and put it into Box 1.

Pick up Ball 3 from Box 1 and put it into Box 3.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

-1

Sample Input 3

5 5
1 2 1
2 1 1
1 3 2
4 5 1
5 4 1

Sample Output 3

6

Sample Input 4

1 1
1 1 1

Sample Output 4

0



Sample input:
3 3
1 2 1
2 1 1
1 3 2


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys

from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


def solve():
    n, m = map(int, sys.stdin.buffer.readline().split())

    extra_durabilities = [0] * n
    self_loop_durabilities = [[] for _ in range(n)]
    outdegrees = [0] * n
    base_operation_count = 0
    uft = UnionFind(n)

    mp = map(int, sys.stdin.buffer.read().split())
    for a, b, c in zip(mp, mp, mp):
        a -= 1
        b -= 1
        outdegrees[a] += 1
        if a == b:
            if c >= 2:
                self_loop_durabilities[a].append(c)
            continue
        uft.unite(a, b)
        extra_durabilities[a] += c - 1
        base_operation_count += 1

    # components[root] = [size, max_outdegree, durability(non-self-loop), self-loop-durability]
    components = defaultdict(lambda: [0, 0, 0, []])
    for i in range(n):
        r = uft._root(i)
        item = components[r]
        item[0] += 1
        item[1] = max(item[1], outdegrees[i])
        item[2] += extra_durabilities[i]
        item[3].extend(self_loop_durabilities[i])

    exists_initial_catalyst_on_moving_path = False
    exists_initial_catalyst_at_self_loop = False
    supplied_catalyst = 0
    demanded_catalyst = 0
    self_loop_catalysts_cost1 = []
    self_loop_catalysts_cost2 = []

    for i, (cnt, deg, dur, sel) in components.items():
        if cnt == 1:
            if deg == 1:
                self_loop_catalysts_cost2.extend(c - 2 for c in sel)
            else:
                self_loop_catalysts_cost1.extend(c - 1 for c in sel)
                exists_initial_catalyst_at_self_loop = True
            continue
        if deg == 1:
            supplied_catalyst += dur
            demanded_catalyst += 1
        else:
            supplied_catalyst += dur
            if dur >= 1:
                exists_initial_catalyst_on_moving_path = True
            elif len(sel) >= 1:
                exists_initial_catalyst_at_self_loop = True
        self_loop_catalysts_cost1.extend(c - 1 for c in sel)

    # print(base_operation_count, supplied_catalyst, demanded_catalyst,
    #       exists_initial_catalyst_on_moving_path, exists_initial_catalyst_at_self_loop)

    if demanded_catalyst == 0:
        return base_operation_count

    if not exists_initial_catalyst_on_moving_path and not exists_initial_catalyst_at_self_loop:
        return -1

    if supplied_catalyst >= demanded_catalyst:
        if exists_initial_catalyst_on_moving_path:
            return base_operation_count + demanded_catalyst
        else:
            return base_operation_count + demanded_catalyst + 1

    self_loop_catalysts_cost1.sort(reverse=True)
    self_loop_catalysts_cost2.sort(reverse=True)
    # print(self_loop_catalysts_cost1)
    # print(self_loop_catalysts_cost2)
    acc1 = [0] + list(accumulate(self_loop_catalysts_cost1))
    acc2 = [0] + list(accumulate(self_loop_catalysts_cost2))
    # print(acc1)
    # print(acc2)
    shortage = demanded_catalyst - supplied_catalyst
    if acc1[-1] + acc2[-1] < shortage:
        return -1

    cost = 10 ** 18
    for use1 in range(0 if exists_initial_catalyst_on_moving_path else 1, len(acc1)):
        cat = acc1[use1]
        remaining = shortage - cat
        if remaining <= 0:
            cost = min(cost, use1)
            break
        if remaining > acc2[-1]:
            continue
        use2 = bisect_left(acc2, remaining)
        cost = min(cost, use1 + 2 * use2)

    return base_operation_count + demanded_catalyst + cost


print(solve())

Submission status: Wrong Answer

Solution code:
import sys

from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


def solve():
    n, m = map(int, sys.stdin.buffer.readline().split())

    extra_durabilities = [0] * n
    self_loop_durabilities = [[] for _ in range(n)]
    outdegrees = [0] * n
    base_operation_count = 0
    uft = UnionFind(n)

    mp = map(int, sys.stdin.buffer.read().split())
    for a, b, c in zip(mp, mp, mp):
        a -= 1
        b -= 1
        outdegrees[a] += 1
        if a == b:
            if c >= 2:
                self_loop_durabilities[a].append(c)
            continue
        uft.unite(a, b)
        extra_durabilities[a] += c - 1
        base_operation_count += 1

    # components[root] = [size, max_outdegree, durability(non-self-loop), self-loop-durability]
    components = defaultdict(lambda: [0, 0, 0, []])
    for i in range(n):
        r = uft._root(i)
        item = components[r]
        item[0] += 1
        item[1] = max(item[1], outdegrees[i])
        item[2] += extra_durabilities[i]
        item[3].extend(self_loop_durabilities[i])

    exists_initial_catalyst = False
    supplied_catalyst = 0
    demanded_catalyst = 0
    self_loop_catalysts_cost1 = []
    self_loop_catalysts_cost2 = []

    for i, (cnt, deg, dur, sel) in components.items():
        if cnt == 1:
            if deg == 1:
                self_loop_catalysts_cost2.extend(c - 2 for c in sel)
            else:
                self_loop_catalysts_cost1.extend(c - 1 for c in sel)
            continue
        if deg == 1:
            supplied_catalyst += dur
            demanded_catalyst += 1
        else:
            supplied_catalyst += dur
            exists_initial_catalyst = True
        self_loop_catalysts_cost1.extend(c - 1 for c in sel)

    if demanded_catalyst == 0:
        return base_operation_count

    if not exists_initial_catalyst:
        return -1

    if supplied_catalyst >= demanded_catalyst:
        return base_operation_count + demanded_catalyst

    self_loop_catalysts_cost1.sort(reverse=True)
    self_loop_catalysts_cost2.sort(reverse=True)
    acc1 = [0] + list(accumulate(self_loop_catalysts_cost1))
    acc2 = [0] + list(accumulate(self_loop_catalysts_cost2))
    shortage = demanded_catalyst - supplied_catalyst
    if acc1[-1] + acc2[-1] < shortage:
        return -1

    cost = 10 ** 18
    for use1, cat in enumerate(acc1):
        remaining = shortage - cat
        if remaining <= 0:
            cost = min(cost, use1)
            break
        if remaining > acc2[-1]:
            continue
        use2 = bisect_left(acc2, remaining)
        cost = min(cost, use1 + 2 * use2)

    return base_operation_count + demanded_catalyst + cost


print(solve())

Submission status: Wrong Answer

Solution code:
import sys

# 箱を頂点とし、A→Bに有向辺を張る
# ①出次数（初期でボールが入っている個数）が全て1以下の、サイズ2以上の連結成分
#   ・分岐のないサイクル（入次数1以上が保証されているため）
#   ・外部から触媒が来ないと動かせない。来たら全て連鎖的に流れる
#   ・流れる途中で Ci>=2 のボールがあればそいつも他の触媒になれる
# ②出次数に2以上のものがある連結成分
#   ・強連結成分分解+トポロジカルソートを考える（実際にやる必要は無い）
#   ・トポロジカル順で最上位になる組は、必ず下位の組に辺が伸びる頂点が出次数2以上
#   ・連鎖的に全てのボールを希望の箱に1回で移せる
#   ・Ci>=2 のボールがあれば他の触媒になれる
# ③自己ループボール
#   ・動かす必要は無いが、Ci>=2なら触媒数が足りなければ触媒になれる
#   ・②に含まれるものは、全体の移動回数を1増やすことでCi-1回触媒を増やせる
#   ・完全に浮いているものはそれ自身を起動するのにも触媒が必要なので、
#     全体の移動回数を2と触媒数1を犠牲にCi-1回触媒を増やせる（差し引きCi-2回）
#
# ①が存在し、かつ②が1つもなければ不可能
# ①が存在しなければ、A!=Bであるボール数
# ①が存在し、初期で②が1つでもあれば、
#   A!=Bであるボール数 + ①の個数 が下限
#   触媒が足りない場合、全体の移動回数を1 or 2増やすことでCi-2回触媒を増やせる
#   →それでも足りなければ不可能
#   →足りるならコストと価値でナップサック問題
#   A!=Bであるボール数 + ①の個数 + 自己ループを触媒に利用するためのコスト

from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


def solve():
    n, m = map(int, sys.stdin.buffer.readline().split())

    extra_durabilities = [0] * n
    self_loop_durabilities = [[] for _ in range(n)]
    outdegrees = [0] * n
    base_operation_count = 0
    uft = UnionFind(n)

    mp = map(int, sys.stdin.buffer.read().split())
    for a, b, c in zip(mp, mp, mp):
        a -= 1
        b -= 1
        outdegrees[a] += 1
        if a == b:
            if c >= 3:
                self_loop_durabilities[a].append(c)
            continue
        uft.unite(a, b)
        extra_durabilities[a] += c - 1
        base_operation_count += 1

    # components[root] = [size, max_outdegree, durability(non-self-loop), self-loop-durability]
    components = defaultdict(lambda: [0, 0, 0, []])
    for i in range(n):
        r = uft._root(i)
        item = components[r]
        item[0] += 1
        item[1] = max(item[1], outdegrees[i])
        item[2] += extra_durabilities[i]
        item[3].extend(self_loop_durabilities[i])

    exists_initial_catalyst = False
    supplied_catalyst = 0
    demanded_catalyst = 0
    self_loop_catalysts_cost1 = []
    self_loop_catalysts_cost2 = []

    for i, (cnt, deg, dur, sel) in components.items():
        if cnt == 1:
            if deg == 1:
                self_loop_catalysts_cost2.extend(c - 2 for c in sel)
            else:
                self_loop_catalysts_cost1.extend(c - 1 for c in sel)
            continue
        if deg == 1:
            supplied_catalyst += dur
            demanded_catalyst += 1
        else:
            supplied_catalyst += dur
            exists_initial_catalyst = True
        self_loop_catalysts_cost1.extend(c - 1 for c in sel)

    if demanded_catalyst == 0:
        return base_operation_count

    if not exists_initial_catalyst:
        return -1

    if supplied_catalyst >= demanded_catalyst:
        return base_operation_count + demanded_catalyst

    self_loop_catalysts_cost1.sort(reverse=True)
    self_loop_catalysts_cost2.sort(reverse=True)
    acc1 = [0] + list(accumulate(self_loop_catalysts_cost1))
    acc2 = [0] + list(accumulate(self_loop_catalysts_cost2))
    shortage = demanded_catalyst - supplied_catalyst
    if acc1[-1] + acc2[-1] < shortage:
        return -1

    cost = 10 ** 18
    for use1, cat in enumerate(acc1):
        remaining = shortage - cat
        if remaining <= 0:
            cost = min(cost, use1)
            break
        if remaining > acc2[-1]:
            continue
        use2 = bisect_left(acc2, remaining)
        cost = min(cost, use1 + 2 * use2)

    return base_operation_count + demanded_catalyst + cost


print(solve())

Submission status: Wrong Answer

Solution code:
import sys

from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


def solve():
    n, m = map(int, sys.stdin.buffer.readline().split())

    extra_durabilities = [0] * n
    self_loop_durabilities = [[] for _ in range(n)]
    outdegrees = [0] * n
    base_operation_count = 0
    uft = UnionFind(n)

    mp = map(int, sys.stdin.buffer.read().split())
    for a, b, c in zip(mp, mp, mp):
        a -= 1
        b -= 1
        outdegrees[a] += 1
        if a == b:
            if c >= 3:
                self_loop_durabilities[a].append(c)
            continue
        uft.unite(a, b)
        extra_durabilities[a] += c - 1
        base_operation_count += 1

    # components[root] = [size, max_outdegree, durability(non-self-loop), self-loop-durability]
    components = defaultdict(lambda: [0, 0, 0, []])
    for i in range(n):
        r = uft._root(i)
        item = components[r]
        item[0] += 1
        item[1] = max(item[1], outdegrees[i])
        item[2] += extra_durabilities[i]
        item[3].extend(self_loop_durabilities[i])

    exists_initial_catalyst = False
    supplied_catalyst = 0
    demanded_catalyst = 0
    self_loop_catalysts_cost1 = []
    self_loop_catalysts_cost2 = []

    for i, (cnt, deg, dur, sel) in components.items():
        if cnt == 1:
            if deg == 1:
                self_loop_catalysts_cost2.extend(c - 2 for c in sel)
            else:
                self_loop_catalysts_cost1.extend(c - 1 for c in sel)
            continue
        if deg == 1:
            supplied_catalyst += dur
            demanded_catalyst += 1
        else:
            supplied_catalyst += dur
            exists_initial_catalyst = True
        self_loop_catalysts_cost1.extend(c - 1 for c in sel)

    if demanded_catalyst == 0:
        return base_operation_count

    if not exists_initial_catalyst:
        return -1

    if supplied_catalyst >= demanded_catalyst:
        return base_operation_count + demanded_catalyst

    self_loop_catalysts_cost1.sort(reverse=True)
    self_loop_catalysts_cost2.sort(reverse=True)
    acc1 = [0] + list(accumulate(self_loop_catalysts_cost1))
    acc2 = [0] + list(accumulate(self_loop_catalysts_cost2))
    shortage = demanded_catalyst - supplied_catalyst
    if acc1[-1] + acc2[-1] < shortage:
        return -1

    cost = 10 ** 18
    for use1, cat in enumerate(acc1):
        remaining = shortage - cat
        if remaining <= 0:
            cost = min(cost, use1)
            break
        use2 = bisect_left(acc2, remaining)
        cost = min(cost, use1 + 2 * use2)

    return base_operation_count + demanded_catalyst + cost


print(solve())

Submission status: Wrong Answer

Solution code:
import sys

from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


def solve():
    n, m = map(int, sys.stdin.buffer.readline().split())

    self_loops = []
    outdegrees = [0] * n
    extra_durabilities = [0] * n
    base_operation_count = 0
    uft = UnionFind(n)

    mp = map(int, sys.stdin.buffer.read().split())
    for a, b, c in zip(mp, mp, mp):
        a -= 1
        b -= 1
        outdegrees[a] += 1
        if a == b:
            if c >= 3:
                self_loops.append(c - 2)
            continue
        uft.unite(a, b)
        extra_durabilities[a] += c - 1
        base_operation_count += 1

    components = defaultdict(lambda: [0, 0, 0])  # uft-root: [vertex_count, max_outdegree, sum_durability]
    for i in range(n):
        r = uft._root(i)
        item = components[r]
        item[0] += 1
        item[1] = max(item[1], outdegrees[i])
        item[2] += extra_durabilities[i]

    exists_initial_catalyst = False
    supplied_catalyst = 0
    demanded_catalyst = 0

    for i, (cnt, deg, dur) in components.items():
        if cnt == 1:
            continue
        if deg == 1:
            supplied_catalyst += dur
            demanded_catalyst += 1
        else:
            supplied_catalyst += dur
            exists_initial_catalyst = True

    if demanded_catalyst == 0:
        return base_operation_count

    if not exists_initial_catalyst:
        return -1

    if supplied_catalyst >= demanded_catalyst:
        return base_operation_count + demanded_catalyst

    self_loops.sort(reverse=True)
    acc = [0] + list(accumulate(self_loops))
    shortage = demanded_catalyst - supplied_catalyst
    if acc[-1] < shortage:
        return -1

    i = bisect_left(acc, shortage)
    return base_operation_count + demanded_catalyst + 2 * i


print(solve())

Submission status: Accepted

Solution code:
import sys

from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


def solve():
    n, m = map(int, sys.stdin.buffer.readline().split())

    extra_durabilities = [0] * n
    self_loop_durabilities = [[] for _ in range(n)]
    outdegrees = [0] * n
    base_operation_count = 0
    uft = UnionFind(n)

    mp = map(int, sys.stdin.buffer.read().split())
    for a, b, c in zip(mp, mp, mp):
        a -= 1
        b -= 1
        outdegrees[a] += 1
        if a == b:
            if c >= 2:
                self_loop_durabilities[a].append(c)
            continue
        uft.unite(a, b)
        extra_durabilities[a] += c - 1
        base_operation_count += 1

    # components[root] = [size, max_outdegree, durability(non-self-loop), self-loop-durability]
    components = defaultdict(lambda: [0, 0, 0, []])
    for i in range(n):
        r = uft._root(i)
        item = components[r]
        item[0] += 1
        item[1] = max(item[1], outdegrees[i])
        item[2] += extra_durabilities[i]
        item[3].extend(self_loop_durabilities[i])

    exists_initial_catalyst_on_moving_path = False
    exists_initial_catalyst_at_self_loop = False
    supplied_catalyst = 0
    demanded_catalyst = 0
    self_loop_catalysts_cost1 = []
    self_loop_catalysts_cost2 = []

    for i, (cnt, deg, dur, sel) in components.items():
        if cnt == 1:
            if deg == 1:
                self_loop_catalysts_cost2.extend(c - 2 for c in sel)
            else:
                if len(sel) >= 1:
                    self_loop_catalysts_cost1.extend(c - 1 for c in sel)
                    exists_initial_catalyst_at_self_loop = True
            continue
        if deg == 1:
            supplied_catalyst += dur
            demanded_catalyst += 1
        else:
            supplied_catalyst += dur
            if dur >= 1:
                exists_initial_catalyst_on_moving_path = True
            elif len(sel) >= 1:
                exists_initial_catalyst_at_self_loop = True
        self_loop_catalysts_cost1.extend(c - 1 for c in sel)

    # print(base_operation_count, supplied_catalyst, demanded_catalyst,
    #       exists_initial_catalyst_on_moving_path, exists_initial_catalyst_at_self_loop)

    if demanded_catalyst == 0:
        return base_operation_count

    if not exists_initial_catalyst_on_moving_path and not exists_initial_catalyst_at_self_loop:
        return -1

    if supplied_catalyst >= demanded_catalyst:
        if exists_initial_catalyst_on_moving_path:
            return base_operation_count + demanded_catalyst
        else:
            return base_operation_count + demanded_catalyst + 1

    self_loop_catalysts_cost1.sort(reverse=True)
    self_loop_catalysts_cost2.sort(reverse=True)
    # print(self_loop_catalysts_cost1)
    # print(self_loop_catalysts_cost2)
    acc1 = [0] + list(accumulate(self_loop_catalysts_cost1))
    acc2 = [0] + list(accumulate(self_loop_catalysts_cost2))
    # print(acc1)
    # print(acc2)
    shortage = demanded_catalyst - supplied_catalyst
    if acc1[-1] + acc2[-1] < shortage:
        return -1

    cost = 10 ** 18
    for use1 in range(0 if exists_initial_catalyst_on_moving_path else 1, len(acc1)):
        cat = acc1[use1]
        remaining = shortage - cat
        if remaining <= 0:
            cost = min(cost, use1)
            break
        if remaining > acc2[-1]:
            continue
        use2 = bisect_left(acc2, remaining)
        cost = min(cost, use1 + 2 * use2)

    return base_operation_count + demanded_catalyst + cost


print(solve())

Submission status: Runtime Error

Solution code:
import sys

from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


def solve():
    n, m = map(int, sys.stdin.buffer.readline().split())

    extra_durabilities = [0] * n
    self_loop_durabilities = [[] for _ in range(n)]
    outdegrees = [0] * n
    base_operation_count = 0
    uft = UnionFind(n)

    mp = map(int, sys.stdin.buffer.read().split())
    for a, b, c in zip(mp, mp, mp):
        a -= 1
        b -= 1
        outdegrees[a] += 1
        if a == b:
            if c >= 2:
                self_loop_durabilities[a].append(c)
            continue
        uft.unite(a, b)
        extra_durabilities[a] += c - 1
        base_operation_count += 1

    # components[root] = [size, max_outdegree, durability(non-self-loop), self-loop-durability]
    components = defaultdict(lambda: [0, 0, 0, []])
    for i in range(n):
        r = uft._root(i)
        item = components[r]
        item[0] += 1
        item[1] = max(item[1], outdegrees[i])
        item[2] += extra_durabilities[i]
        item[3].extend(self_loop_durabilities[i])

    exists_initial_catalyst = False
    supplied_catalyst = 0
    demanded_catalyst = 0
    self_loop_catalysts_cost1 = []
    self_loop_catalysts_cost2 = []

    for i, (cnt, deg, dur, sel) in components.items():
        if cnt == 1:
            if deg == 1:
                self_loop_catalysts_cost2.extend(c - 2 for c in sel)
            else:
                self_loop_catalysts_cost1.extend(c - 1 for c in sel)
                exists_initial_catalyst = True
            continue
        if deg == 1:
            supplied_catalyst += dur
            demanded_catalyst += 1
        else:
            supplied_catalyst += dur
            if dur >= 1 or sel:
                exists_initial_catalyst = True
        self_loop_catalysts_cost1.extend(c - 1 for c in sel)

    # print(base_operation_count, supplied_catalyst, demanded_catalyst, exists_initial_catalyst)

    if demanded_catalyst == 0:
        return base_operation_count

    if not exists_initial_catalyst:
        return -1

    if supplied_catalyst >= demanded_catalyst:
        return base_operation_count + demanded_catalyst

    self_loop_catalysts_cost1.sort(reverse=True)
    self_loop_catalysts_cost2.sort(reverse=True)
    # print(self_loop_catalysts_cost1)
    # print(self_loop_catalysts_cost2)
    acc1 = list(accumulate(self_loop_catalysts_cost1))
    acc2 = [0] + list(accumulate(self_loop_catalysts_cost2))
    # print(acc1)
    # print(acc2)
    shortage = demanded_catalyst - supplied_catalyst
    if acc1[-1] + acc2[-1] < shortage:
        return -1

    cost = 10 ** 18
    for use1, cat in enumerate(acc1, start=1):
        remaining = shortage - cat
        if remaining <= 0:
            cost = min(cost, use1)
            break
        if remaining > acc2[-1]:
            continue
        use2 = bisect_left(acc2, remaining)
        cost = min(cost, use1 + 2 * use2)

    return base_operation_count + demanded_catalyst + cost


print(solve())

Submission status: Runtime Error

Solution code:
import sys

from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


def solve():
    n, m = map(int, sys.stdin.buffer.readline().split())

    extra_durabilities = [0] * n
    self_loop_durabilities = [[] for _ in range(n)]
    outdegrees = [0] * n
    base_operation_count = 0
    uft = UnionFind(n)

    mp = map(int, sys.stdin.buffer.read().split())
    for a, b, c in zip(mp, mp, mp):
        a -= 1
        b -= 1
        outdegrees[a] += 1
        if a == b:
            if c >= 2:
                self_loop_durabilities[a].append(c)
            continue
        uft.unite(a, b)
        extra_durabilities[a] += c - 1
        base_operation_count += 1

    # components[root] = [size, max_outdegree, durability(non-self-loop), self-loop-durability]
    components = defaultdict(lambda: [0, 0, 0, []])
    for i in range(n):
        r = uft._root(i)
        item = components[r]
        item[0] += 1
        item[1] = max(item[1], outdegrees[i])
        item[2] += extra_durabilities[i]
        item[3].extend(self_loop_durabilities[i])

    exists_initial_catalyst = False
    supplied_catalyst = 0
    demanded_catalyst = 0
    self_loop_catalysts_cost1 = []
    self_loop_catalysts_cost2 = []

    for i, (cnt, deg, dur, sel) in components.items():
        if cnt == 1:
            if deg == 1:
                self_loop_catalysts_cost2.extend(c - 2 for c in sel)
            else:
                self_loop_catalysts_cost1.extend(c - 1 for c in sel)
            continue
        if deg == 1:
            supplied_catalyst += dur
            demanded_catalyst += 1
        else:
            supplied_catalyst += dur
            if dur >= 1:
                exists_initial_catalyst = True
        self_loop_catalysts_cost1.extend(c - 1 for c in sel)

    if demanded_catalyst == 0:
        return base_operation_count

    if not exists_initial_catalyst:
        return -1

    if supplied_catalyst >= demanded_catalyst:
        return base_operation_count + demanded_catalyst

    self_loop_catalysts_cost1.sort(reverse=True)
    self_loop_catalysts_cost2.sort(reverse=True)
    # print(base_operation_count, supplied_catalyst, demanded_catalyst)
    # print(self_loop_catalysts_cost1)
    # print(self_loop_catalysts_cost2)
    acc1 = list(accumulate(self_loop_catalysts_cost1))
    acc2 = [0] + list(accumulate(self_loop_catalysts_cost2))
    # print(acc1)
    # print(acc2)
    shortage = demanded_catalyst - supplied_catalyst
    if acc1[-1] + acc2[-1] < shortage:
        return -1

    cost = 10 ** 18
    for use1, cat in enumerate(acc1, start=1):
        remaining = shortage - cat
        if remaining <= 0:
            cost = min(cost, use1)
            break
        if remaining > acc2[-1]:
            continue
        use2 = bisect_left(acc2, remaining)
        cost = min(cost, use1 + 2 * use2)

    return base_operation_count + demanded_catalyst + cost


print(solve())