問題一覧 > 通常問題

No.3087 University Coloring

レベル : / AI推定難易度 : 1150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 89
作問者 : yuusaan / テスター : 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 12068 / 自分の提出
問題文最終更新日: 2025-04-04 10:22:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 463 (順位表) の他の問題:

Problem Statement

Koyaso National University has $N$ plazas, numbered $1,2,\dots, N$. Each plaza has a Koyaso statue. Initially, none of the Koyaso statues are painted.

There are also $M$ passages, numbered $1,2,\dots , M$. Passage $i$ connects plazas $a,b$ and has length $c$. It is guaranteed that every plaza can be reached from plaza $1$ by traversing passages $0$ or more times.

Yu is initially at plaza $1$, and has painted the Koyaso statue in plaza $1$ blue.

From now on, Yu may perform the following actions any number of times. Regarding the "card pile" mentioned in the description, the pile initially contains no cards.


  • Action $1$: Choose a plaza that is directly connected to the current plaza by a passage and whose Koyaso statue has not been painted yet, move there, and paint the Koyaso statue at the destination blue. At this time, letting $x$ be the number of the passage used, place $1$ card with $x$ written on it on top of the card pile.

  • Action $2$: Paint the Koyaso statue in the current plaza purple, remove the top card of the card pile, and traverse the passage whose number is written on the removed card. It can be proved that one end of this passage is always the current plaza (that is, this passage can be traversed from the current plaza).
    However, if no cards remain in the pile, Yu declares the end immediately after painting the Koyaso statue and performs no further actions.


Find the maximum possible total distance Yu has moved at the time Yu declares the end. Movement within a plaza is not counted.

Input

$N\ M$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$\vdots$
$a_M\ b_M\ c_M$

Constraints

  • $2\le N\le 2\times 10^5$
  • $1\le M\le \min(\frac{N(N-1)}{2},2\times 10^5)$
  • $1\le a_i< b_i \le N$
  • $1\le c_i \le 10^9$
  • $a_i \neq b_i$
  • If $i\neq j$, then $(a_i,b_i)\neq (a_j,b_j)$
  • Every plaza can be reached from plaza $1$ by traversing passages $0$ or more times.
  • All inputs are integers.

Output

Print a newline at the end.

Sample

Sample 1
Input
3 3
1 2 1
2 3 2
1 3 3
Output
10

For example, the following sequences of actions are possible.

  • Plaza $1$ → (Action $1$) Plaza $2$ → (Action $1$) Plaza $3$ → (Action $2$) Plaza $2$ → (Action $2$) Plaza $1$ → (Action $2$) End
  • Plaza $1$ → (Action $1$) Plaza $3$ → (Action $1$) Plaza $2$ → (Action $2$) Plaza $3$ → (Action $2$) Plaza $1$ → (Action $2$) End

For the former sequence of actions, the total distance moved is $6$. For the latter, it is $10$. Since the total distance moved cannot exceed $10$ for any sequence of moves, print $10$.

Sample 2
Input
4 5
1 2 4
2 3 6
3 4 8
1 3 10
2 4 10
Output
56

Sample 3
Input
6 5
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
Output
10000000000

Note that the answer may not fit in a $32$-bit integer type.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。