Taco - Minimum Travel Time

You are given an undirected weighted graph with n nodes and m edges. The nodes represent locations and the edges represent roads between them, with an associated travel time. The journey must start at the main hub (node 0), visit every other node at least once, and return to node 0 in the minimum possible total travel time.

Your task is to compute the minimum travel time required for this journey. Mathematically, if the visited node sequence is \(v_0, v_1, \dots, v_k, v_{k+1}\) where \(v_0 = v_{k+1} = 0\) and \(\{v_1,\dots,v_k\} = \{1, 2, \dots, n-1\}\), you need to minimize \[ T = \sum_{i=0}^{k} d_{v_i, v_{i+1}}, \] where \(d_{u,v}\) is the travel time between node \(u\) and \(v\).

Note: It is guaranteed that a valid route exists. The number of nodes is small enough that a brute force solution exploring all permutations of nodes is sufficient.

inputFormat

The input is read from stdin and has the following format:

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

Here, n is the number of nodes, m is the number of edges, and each of the following m lines contains three integers u, v, and w, representing an edge between nodes u and v with a travel time of w.

outputFormat

The output should be written to stdout and consist of a single integer: the minimum total travel time required to start at node 0, visit all other nodes at least once, and return to node 0.

4 4
0 1 10
1 2 10
2 3 10
3 0 10

40