Minimum Tour Time

Ash wishes to visit all tourist attractions in his city. The city has n attractions and m bidirectional roads connecting some of these attractions. Each road has a travel time associated with it.

Ash starts his journey at attraction 1 and must visit every attraction at least once before returning to attraction 1. His goal is to minimize the total travel time. If such a tour is impossible, output -1.

This problem can be modeled as the Travelling Salesman Problem (TSP). One may use dynamic programming with bitmasking. Let \(dp[i][mask]\) denote the minimum travel time to reach attraction \(i\) having visited the set of attractions represented by \(mask\). The recurrence for the DP is: \[ dp[i][mask] = \min_{j \in mask \setminus \{i\}} \Big(dp[j][mask \setminus \{i\}] + cost(j, i)\Big) \]

inputFormat

The input is given via stdin. The first line contains two integers n and m, which denote the number of attractions and the number of roads respectively. The next m lines each contain three integers u, v, and t, representing a road between attractions u and v with travel time t.

outputFormat

Output the minimum travel time required for Ash to complete his tour. If no such tour exists, output -1. The result should be printed to stdout.## sample

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

80