P5234 [JSOI2012] Prison Break: Laohuqiao

This is beautiful Nanjing. This is the graceful Jinxiang River. This is the cozy Laohuqiao. If we say the beauty of the Jinxiang River lies in its pleasant scenery, it is better to say it lies in the relaxed, old-classical-alley style of life in Nanjing. If we say the Jinxiang River is charming because of its simple folk customs, it is better to say it is the secrets buried by history that attract people’s curiosity. Perhaps many people still remember Laohuqiao Prison, the largest prison in Jiangnan during the Beiyang period. Over nearly a century, through the rise and fall of several eras such as the Late Qing, Beiyang, the Republic of China, and New China, its name changed again and again, showing all its vicissitudes. People today may find it hard to believe how many thrilling events once took place right here.

It was the winter of $1948$. A small team from an underground organization in Nanjing decided to raid Laohuqiao Prison to rescue several hundred trapped people. At that time, Laohuqiao Prison was surrounded by $N$ layers of power grids, numbered from inside to outside as $1, 2, \dots, N$. The $1$st layer of the power grid was connected to high-voltage electricity. There were $M$ high-voltage wires connecting all the grids. The $i$-th wire connected the $a_i$-th and $b_i$-th layers, and to destroy the $i$-th wire, at least $T_i$ agents were needed. Facing so many layers of grids, the raiding team was troubled. They must destroy at least one layer of the power grid, otherwise the raid cannot succeed. However, a cunning spy learned about this. To sabotage the raid plan, the enemy secretly added one more high-voltage wire without letting the team members discover it. To ensure success, no matter which two layers this newly added secret high-voltage wire connects, the team must destroy exactly one high-voltage wire so that at least one layer of the power grid becomes unpowered. Note that for the newly added wire, we do not know how many agents are needed to destroy it successfully. The question is: what is the minimum number of agents the team must have? The decisive battle is tonight!

The first line contains $2$ integers, $N$ and $M$, representing the number of grid layers and the number of high-voltage wires. The next $M$ lines each contain $3$ integers: $a_i$, $b_i$, and $T_i$.

Output only one line containing one integer, which is the minimum number of agents needed. If the plan is bound to fail, output $-1$.

For $30\%$ of the testdata, $N \leq 200$, $M \leq 250$. For $70\%$ of the testdata, $N \leq 50000$, $M \leq 100000$. For $100\%$ of the testdata, $N \leq 500000$, $M \leq 1000000$, $T \leq 100000$. For the second sample, the newly added high-voltage wire can only appear between $2$ and $3$, between $2$ and $4$, or between $3$ and $4$. If it appears between $2$ and $3$, then the only wire that can be destroyed is the one between $1$ and $4$. If it appears between $2$ and $4$, then the only wire that can be destroyed is the one between $1$ and $3$. If it appears between $3$ and $4$, then the only wire that can be destroyed is the one between $1$ and $2$. Therefore, at least $3$ agents are needed to handle all possible cases. Translated by ChatGPT 5