{"raw_statement":[{"iden":"problem statement","content":"Mole decided to live in an abandoned mine. The structure of the mine is represented by a simple connected undirected graph which consists of $N$ vertices numbered $1$ through $N$ and $M$ edges. The $i$\\-th edge connects Vertices $a_i$ and $b_i$, and it costs $c_i$ yen (the currency of Japan) to remove it.\nMole would like to remove some of the edges so that there is exactly one path from Vertex $1$ to Vertex $N$ that does not visit the same vertex more than once. Find the minimum budget needed to achieve this."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 15$\n*   $N-1 \\leq M \\leq N(N-1)/2$\n*   $1 \\leq a_i, b_i \\leq N$\n*   $1 \\leq c_i \\leq 10^{6}$\n*   There are neither multiple edges nor self-loops in the given graph.\n*   The given graph is connected."},{"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$:$\n$a_M$ $b_M$ $c_M$"},{"iden":"sample input 1","content":"4 6\n1 2 100\n3 1 100\n2 4 100\n4 3 100\n1 4 100\n3 2 100"},{"iden":"sample output 1","content":"200\n\nBy removing the two edges represented by the red dotted lines in the figure below, the objective can be achieved for a cost of $200$ yen.\n\n![image](https://atcoder.jp/img/arc078/45c15676bb602ca3b762561fc014ecd0.png)"},{"iden":"sample input 2","content":"2 1\n1 2 1"},{"iden":"sample output 2","content":"0\n\nIt is possible that there is already only one path from Vertex $1$ to Vertex $N$ in the beginning."},{"iden":"sample input 3","content":"15 22\n8 13 33418\n14 15 55849\n7 10 15207\n4 6 64328\n6 9 86902\n15 7 46978\n8 14 53526\n1 2 8720\n14 12 37748\n8 3 61543\n6 5 32425\n4 11 20932\n3 12 55123\n8 2 45333\n9 12 77796\n3 9 71922\n12 15 70793\n2 4 25485\n11 6 1436\n2 7 81563\n7 11 97843\n3 1 40491"},{"iden":"sample output 3","content":"133677"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}