Traveling Salesman Problem with Minimum Travel Time

You are given a complete description of a road network between n intersections and m bidirectional roads. Each road connects two intersections with a travel time cost. Your task is to find the minimum travel time required for a tourist to start at intersection 1, visit every other intersection exactly once, and return to the starting point.

The travel time of a journey is the sum of the weights corresponding to the roads used. In other words, if a journey uses roads with costs \(w_1, w_2, \ldots, w_k\), the total travel time is:

You may assume that the graph is such that there is always a valid route which visits all intersections exactly once and returns to the start.

inputFormat

The first line of input contains two integers \(n\) and \(m\) where \(n\) is the number of intersections and \(m\) is the number of roads. Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\) representing a bidirectional road between intersections \(u\) and \(v\) with travel time \(w\).

outputFormat

Output a single integer: the minimum travel time required to start at intersection 1, visit all intersections exactly once, and return to intersection 1.

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

80