E - Fragile Balls Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 12001200

問題文

11 から NN までの番号の付いた NN 個の箱があります. また,11 から MM までの番号の付いた MM 個のボールがあります. 現在,ボール ii は箱 AiA_i に入っています.

あなたは,以下の操作を行えます.

  • 現在ボールが 22 個以上入っている箱を 11 つ選ぶ. そして,その箱からボールを 11 つ選んで取り出し,別の箱に入れる.

ただし,ボールは非常に壊れやすいため,ボール ii は合計で CiC_i 回より多く移動させることはできません. 逆に,ボールが壊れない限り,何度でもボールの移動は行なえます.

あなたの目標は,すべての ii (1iM1 \leq i \leq M)について,ボール ii が箱 BiB_i に入っているようにすることです. この目的が達成可能かどうか判定してください. また可能な場合は,目標を達成するのに必要な操作回数の最小値を求めてください.

制約

  • 1N1051 \leq N \leq 10^5
  • 1M1051 \leq M \leq 10^5
  • 1Ai,BiN1 \leq A_i,B_i \leq N
  • 1Ci1051 \leq C_i \leq 10^5
  • 目標とする状態において,どの箱にも 11 つ以上のボールが入っている. つまり,すべての ii (1iN1 \leq i \leq N) について,Bj=iB_j=i を満たす jj が存在する.

入力

入力は以下の形式で標準入力から与えられる.

NN MM
A1A_1 B1B_1 C1C_1
A2A_2 B2B_2 C2C_2
\vdots
AMA_M BMB_M CMC_M

出力

目標が達成不可能な場合は 1-1 を,達成可能な場合は必要な操作回数の最小値を出力せよ.


入力例 1Copy

Copy
3 3
1 2 1
2 1 1
1 3 2

出力例 1Copy

Copy
3

以下のように 33 回の操作を行えば良いです.

  • 11 からボール 11 を取り出し,箱 22 に入れる.
  • 22 からボール 22 を取り出し,箱 11 に入れる.
  • 11 からボール 33 を取り出し,箱 33 に入れる.

入力例 2Copy

Copy
2 2
1 2 1
2 1 1

出力例 2Copy

Copy
-1

入力例 3Copy

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

出力例 3Copy

Copy
6

入力例 4Copy

Copy
1 1
1 1 1

出力例 4Copy

Copy
0

Score : 12001200 points

Problem Statement

We have NN boxes numbered 11 to NN, and MM balls numbered 11 to MM. Currently, Ball ii is in Box AiA_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 ii more than CiC_i times in total. Within this limit, you can do the operation any number of times.

Your objective is to have Ball ii in Box BiB_i for every ii (1iM1 \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

  • 1N1051 \leq N \leq 10^5
  • 1M1051 \leq M \leq 10^5
  • 1Ai,BiN1 \leq A_i,B_i \leq N
  • 1Ci1051 \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 ii (1iN1 \leq i \leq N), there exists jj such that Bj=iB_j=i.

Input

Input is given from Standard Input in the following format:

NN MM
A1A_1 B1B_1 C1C_1
A2A_2 B2B_2 C2C_2
\vdots
AMA_M BMB_M CMC_M

Output

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


Sample Input 1Copy

Copy
3 3
1 2 1
2 1 1
1 3 2

Sample Output 1Copy

Copy
3

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

  • Pick up Ball 11 from Box 11 and put it into Box 22.
  • Pick up Ball 22 from Box 22 and put it into Box 11.
  • Pick up Ball 33 from Box 11 and put it into Box 33.

Sample Input 2Copy

Copy
2 2
1 2 1
2 1 1

Sample Output 2Copy

Copy
-1

Sample Input 3Copy

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

Sample Output 3Copy

Copy
6

Sample Input 4Copy

Copy
1 1
1 1 1

Sample Output 4Copy

Copy
0


2025-03-29 (Sat)
14:59:58 +00:00