{"problem":{"name":"Remembering the Days","description":{"content":"A region has $N$ towns numbered $1$ to $N$, and $M$ roads numbered $1$ to $M$. The $i$\\-th road connects town $A_i$ and town $B_i$ bidirectionally with length $C_i$. Find the maximum possible total le","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc317_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc317_c","tags":[],"sample_group":[["4 4\n1 2 1\n2 3 10\n1 3 100\n1 4 1000","1110\n\nIf you travel as $4\\to 1\\to 3\\to 2$, the total length of the roads you traverse is $1110$."],["10 1\n5 9 1","1\n\nThere may be a town that is not connected to a road."],["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","20\n\n![image](https://img.atcoder.jp/abc317/06ac62d13dd1c4b2b469a524a60eb093.png)"]],"created_at":"2026-03-03 11:01:14"}}