{"raw_statement":[{"iden":"problem statement","content":"A region has $N$ towns numbered $1$ to $N$, and $M$ roads numbered $1$ to $M$.\nThe $i$\\-th road connects town $A_i$ and town $B_i$ bidirectionally with length $C_i$.\nFind the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10$\n*   $1 \\leq M \\leq \\frac{N(N-1)}{2}$\n*   $1 \\leq A_i < B_i \\leq N$\n*   The pairs $(A_i,B_i)$ are distinct.\n*   $1\\leq C_i \\leq 10^8$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $C_1$\n$\\vdots$\n$A_M$ $B_M$ $C_M$"},{"iden":"sample input 1","content":"4 4\n1 2 1\n2 3 10\n1 3 100\n1 4 1000"},{"iden":"sample output 1","content":"1110\n\nIf you travel as $4\\to 1\\to 3\\to 2$, the total length of the roads you traverse is $1110$."},{"iden":"sample input 2","content":"10 1\n5 9 1"},{"iden":"sample output 2","content":"1\n\nThere may be a town that is not connected to a road."},{"iden":"sample input 3","content":"10 13\n1 2 1\n1 10 1\n2 3 1\n3 4 4\n4 7 2\n4 8 1\n5 8 1\n5 9 3\n6 8 1\n6 9 5\n7 8 1\n7 9 4\n9 10 3"},{"iden":"sample output 3","content":"20\n\n![image](https://img.atcoder.jp/abc317/06ac62d13dd1c4b2b469a524a60eb093.png)"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}