Maximum Treasure Collection on a Cactus Archipelago

You are given an undirected connected graph with n islands (numbered from 1 to n) and m fragile bridges. Island 1 is the only inhabited island. Each bridge connects two different islands and there is at most one bridge between any two islands. Each bridge i has an associated treasure value \(w_i\). However, these bridges are so weak that they collapse immediately after one use.

A safe island exploration path is one that does not traverse any collapsed bridge. An interesting island exploration loop is defined as a safe path that starts and ends at the same island, visits at least two different islands, and (except for the starting island, which appears twice) every other island appears at most once. Moreover, for any fixed starting island, any two different interesting loops do not share the same bridge.

You may choose any island as the landing point to begin your adventure and collect treasures along the way. However, to ensure your safety, you must finish your journey by returning to island 1. With the constraint that each bridge can only be used once, determine the maximum total treasure value you can possibly collect while guaranteeing a safe return (that is, you must form a closed walk starting and ending at island 1 that obeys the rules).

Note: Owing to the special property of the bridges, the graph always satisfies the following: any two islands are reachable, and the bridges are arranged in such a way that if one considers all interesting loops starting at the same island, no bridge is used in more than one loop. In fact, the overall graph is a cactus graph (each edge belongs to at most one simple cycle). In the context of this problem, a valid adventure is equivalent to selecting a subset of bridges (each used at most once) whose union forms a connected subgraph containing island 1 in which every vertex used has even degree (thus it can be traversed by a closed trail) and the subgraph contains at least one bridge. Your task is to compute the maximum sum of treasure values of such a selection.

Input details: The first line contains two integers n and m. Each of the next m lines contains three integers u, v and w indicating that there is a bridge connecting islands u and v with treasure value w.

Output details: Output a single integer --- the maximum total treasure value you can collect under the safety constraints. If no valid route exists, output 0.

inputFormat

The input consists of multiple lines. The first line contains two integers n and m (\(2 \le n \le 10\), \(1 \le m \le 15\)) --- the number of islands and the number of bridges, respectively. Each of the following m lines contains three integers \(u\), \(v\) and \(w\) (\(1 \le u, v \le n, u \neq v, 1 \le w \le 10^4\)), describing a bridge connecting islands \(u\) and \(v\) with treasure value \(w\). It is guaranteed that the original graph is connected and satisfies the cactus property as described in the statement.

outputFormat

Output a single integer representing the maximum total treasure value that can be collected under the given conditions.

sample

3 3
1 2 10
2 3 5
3 1 7

22