Traveling Salesman Problem on Clearings

You are given a set of N clearings in a forest and M bidirectional paths connecting them. Each path connects two distinct clearings with an associated weight. The clearings are numbered from 1 to N. Your task is to find the shortest route that starts at clearing 1, visits every clearing exactly once, and returns to clearing 1.

The total distance of a route is the sum of the weights of the paths used. Formally, if a route is represented as a sequence of vertices \(v_1, v_2, \ldots, v_N, v_{N+1}\) where \(v_1 = v_{N+1} = 1\) and \(\{v_2, \ldots, v_N\}\) is a permutation of \(\{2, 3, \ldots, N\}\), then the total cost is:

[ \text{Cost} = \sum_{i=1}^{N} d(v_i, v_{i+1}) ]

It is guaranteed that there exists a direct path between any two clearings (i.e. the graph is complete).

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two integers N and M where \(1 \leq N \leq 10\) and M is the number of paths.
2. Each of the following M lines contains three integers \(u\), \(v\), and \(w\) (with \(1 \le u, v \le N\) and \(w > 0\)), representing a bidirectional path between clearings \(u\) and \(v\) with weight \(w\).

Note that since the graph is complete, for a graph with N clearings, typically \(M = \frac{N(N-1)}{2}\).

outputFormat

Print a single integer to standard output (stdout) representing the length of the shortest route that starts at clearing 1, visits each clearing exactly once, and returns to clearing 1.

4 6
1 2 10
1 3 15
1 4 20
2 3 35
2 4 25
3 4 30

80