Shortest Cycle in a Checkpoint Network

You are given a network of N checkpoints and M roads connecting them. Each road is described by three integers u, v and d, which means there is an undirected road between checkpoint u and checkpoint v with distance d.

Your task is to compute the shortest possible cycle (a closed route) which starts at a checkpoint, visits every checkpoint at least once and returns to the starting checkpoint. If such a cycle does not exist, output -1. Note that when N = 1, the shortest cycle is 0.

This problem can be modeled as a variation of the Traveling Salesman Problem (TSP) utilizing bit mask dynamic programming. The transition function is given by:

$$dp[mask][i] = \min_{j \ not\ in\ mask} \{ dp[mask \cup \{j\}][j] = dp[mask][i] + d_{i,j} \} $$

Finally, the answer is the minimum value among all possible cycles that cover all nodes and return to the starting node.

inputFormat

The first line contains two integers N and M where N is the number of checkpoints and M is the number of roads.

The following M lines each contain three integers u, v, and d describing a road between checkpoint u and checkpoint v with distance d.

outputFormat

Output a single integer representing the minimum distance of a cycle that visits all checkpoints and returns to the starting point. If no such cycle exists, print -1.

## sample

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

70