{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"3 3\n1 2 1\n2 3 2\n1 3 10"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"4 6\n1 2 1\n1 3 1\n1 4 1\n2 3 1\n2 4 1\n3 4 1"},{"iden":"sample output 2","content":"3 1 2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}