H. Harmony Graph
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Do you know what an Eulerian circuit is? An Eulerian circuit is a (possibly non-simple) cycle that uses each edge exactly once. It can be defined for both undirected and directed graphs. In this problem, we focus on the directed case.

We define a graph as harmony if:

  • It contains exactly one Eulerian circuit.

Here, two Eulerian circuits are considered the same if they are identical up to rotation. In particular, a graph with no edges is also considered harmony. See the following figure for example.

You are given a directed graph with weighted edges. Your task is to find the harmony subgraph (a subgraph that is harmony) with the maximum total edge weight. A harmony subgraph with no edges is considered to have weight zero.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ — the number of vertices and the number of directed edges.

Each of the next $$$M$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ — representing a directed edge from node $$$u_i$$$ to node $$$v_i$$$ with weight $$$w_i$$$.

  • $$$1 \leq N \leq 14$$$
  • $$$0 \leq M \leq N \cdot (N - 1)$$$
  • $$$1 \leq u_i, v_i \leq N$$$
  • $$$-10^7 \leq w_i \leq 10^7$$$
  • The graph contains no self-loops and no multiple edges.
Output

Output a single integer — the maximum total edge weight among all harmony subgraphs of the given graph.

Examples
Input
4 6
1 2 1
2 1 2
1 3 3
3 1 4
1 4 5
4 1 6
Output
18
Input
3 3
1 2 -1
2 3 -1
3 1 -1
Output
0