Minimum Travel Time

You are given n warehouses and m bidirectional routes connecting them. Each route connects two warehouses and has an associated travel time. The task is to determine the minimum travel time required to start from warehouse 1, visit every warehouse exactly once, and return to warehouse 1.

If it is impossible to visit all warehouses (i.e. a complete round trip does not exist), you should output \(-1\).

Note: This is essentially the Traveling Salesman Problem (TSP) solved through brute-force enumeration. The challenge is feasible only for small \( n \).

inputFormat

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

• The first line contains two integers \( n \) and \( m \): the number of warehouses and the number of routes.
• The following \( m \) lines each contain three integers \( u \), \( v \), and \( t \), which denote a bidirectional route between warehouses \( u \) and \( v \) with travel time \( t \).

outputFormat

Output a single integer to standard output (stdout): the minimum travel time for a complete round trip starting and ending at warehouse 1 while visiting each warehouse exactly once. If no such round trip 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>