P4408 [NOI2003] Truant Child / Data Generator

The phone at Chris's home rang, and Chris's teacher spoke anxiously: "Hello, is this Chris's parent? Your child skipped class again. Does he not want to take the exam?" Hearing about an exam, Chris's parents became very worried. They decided to find Chris in the shortest possible time. They told the teacher: "Based on past experience, Chris must be hiding at his friend Shermie or Yashiro's home, secretly playing The King of Fighters. Now, we'll set out from home to find Chris. As soon as we find him, we'll call you." With a bang, they hung up. Chris's city consists of $N$ residential points and several undirected streets connecting them. It takes $T_{x}$ minutes to traverse street $x$. It is guaranteed that between any two residential points there is exactly one path. Chris's home is at point $C$, and Shermie and Yashiro live at points $A$ and $B$, respectively. Both the teacher and Chris's parents have the city map, but only Chris's parents know the exact locations of $A$, $B$, and $C$; the teacher does not. To find Chris as quickly as possible, Chris's parents will follow these two rules: 1. If the distance from $A$ to $C$ is shorter than the distance from $B$ to $C$, then Chris's parents will first go to Shermie's home to look for Chris. If he is not there, they will then go to Yashiro's home; and vice versa. 2. Chris's parents always walk along the unique path between two points. Clearly, the teacher knows that Chris's parents will follow the above two rules during their search. However, since he does not know the exact locations of $A$, $B$, and $C$, he would like you to tell him: in the worst case, how long will it take Chris's parents to find Chris?

The first line of the input contains two integers $N$ and $M$, representing the total number of residential points and the total number of streets, respectively. Each of the next $M$ lines describes one street. Line $i+1$ contains integers $U_{i}$, $V_{i}$, and $T_{i}$, indicating that street $i$ connects residential points $U_{i}$ and $V_{i}$, and it takes $T_{i}$ minutes to traverse street $i$. No street information is given more than once.

Output a single integer $T$, the number of minutes Chris's parents will need in the worst case to find Chris.

For $100\%$ of the testdata, $3 \le N \le 2\times 10^5$, $1 \le U_{i},V_{i} \le N$, $0 \le T_{i} \le 10^{9}$. Translated by ChatGPT 5