{"problem":{"name":"Road Reduction","description":{"content":"The Kingdom of AtCoder has $N$ cities called City $1,2,\\ldots,N$ and $M$ roads called Road $1,2,\\ldots,M$.   Road $i$ connects Cities $A_i$ and $B_i$ bidirectionally and has a length of $C_i$.   One c","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc252_e"},"statements":[{"statement_type":"Markdown","content":"The Kingdom of AtCoder has $N$ cities called City $1,2,\\ldots,N$ and $M$ roads called Road $1,2,\\ldots,M$.  \nRoad $i$ connects Cities $A_i$ and $B_i$ bidirectionally and has a length of $C_i$.  \nOne can travel between any two cities using some roads.\nUnder financial difficulties, the kingdom has decided to maintain only $N-1$ roads so that one can still travel between any two cities using those roads and abandon the rest.\nLet $d_i$ be the total length of the roads one must use when going from City $1$ to City $i$ using only maintained roads. Print a choice of roads to maintain that minimizes $d_2+d_3+\\ldots+d_N$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2\\times 10^5$\n*   $N-1 \\leq M \\leq 2\\times 10^5$\n*   $1 \\leq A_i < B_i \\leq N$\n*   $(A_i,B_i)\\neq(A_j,B_j)$ if $i\\neq j$.\n*   $1\\leq C_i \\leq 10^9$\n*   One can travel between any two cities using some roads.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_M$ $B_M$ $C_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc252_e","tags":[],"sample_group":[["3 3\n1 2 1\n2 3 2\n1 3 10","1 2\n\nHere are the possible choices of roads to maintain and the corresponding values of $d_i$.\n\n*   Maintain Road $1$ and $2$: $d_2=1$, $d_3=3$.\n*   Maintain Road $1$ and $3$: $d_2=1$, $d_3=10$.\n*   Maintain Road $2$ and $3$: $d_2=12$, $d_3=10$.\n\nThus, maintaining Road $1$ and $2$ minimizes $d_2+d_3$."],["4 6\n1 2 1\n1 3 1\n1 4 1\n2 3 1\n2 4 1\n3 4 1","3 1 2"]],"created_at":"2026-03-03 11:01:14"}}