Kingdom's Traveling Salesman Journey

In a hypothetical kingdom, there are \(n\) cities connected by \(m\) bidirectional roads. The king wishes to embark on a journey starting at city 1, visiting every city exactly once and returning to city 1. Such a cycle is known as a Hamiltonian cycle. The goal of this problem is to determine the minimum travel time required to complete this journey, which is a classic instance of the Traveling Salesman Problem (TSP).

The problem can be formalized as follows:
Given a complete graph where some edges might be missing, find a cycle that visits every vertex exactly once and returns to the origin, minimizing the total travel time. In mathematical terms, you are to compute \[ \min_{\text{cycle}} \sum_{i=1}^{n} w(v_i, v_{i+1}) \] where \(v_{n+1} = v_1\) and \(w(u, v)\) is the travel time between cities \(u\) and \(v\). If no such cycle exists, output -1.

inputFormat

Input is provided via standard input (stdin) in the following format:

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

Here, the first line contains two integers \(n\) (the number of cities) and \(m\) (the number of roads). Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) representing a bidirectional road between cities \(u\) and \(v\) with travel time \(w\). Cities are numbered from 1 to \(n\).

outputFormat

Output a single integer on standard output (stdout): the minimum total travel time to complete the Hamiltonian cycle. If no such cycle exists, output -1.

## sample

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

80

</p>