Bottleneck Travelling Salesman Problem (Small)

The Traveling Salesman Problem (TSP) is one of the most important problems in computer science. Consider one of its variants, the Bottleneck Traveling Salesman Problem (BTSP).

You are given a directed graph with $N$ vertices and $M$ weighted edges. Starting at some vertex, you want to find a tour that visits each of the other $N-1$ vertices exactly once and returns to the starting vertex. There can be several such tours, and you want to minimize the maximum edge cost along the tour.

Given a graph, find a tour that visits every vertex while minimizing the maximum edge cost.

The first line contains the number of vertices $N$ and the number of edges $M$. ($2 \le N \le 9$, $0 \le M \le N(N-1)$)

The next $M$ lines each contain three integers $u$, $v$, $c$ describing an edge. This means there is an edge from vertex $u$ to vertex $v$ with cost $c$. No two edges in the same direction connect the same pair of vertices. ($1 \le u, v \le N$, $u \ne v$, $1 \le c \le 5 \, 000 \, 000$)

If a tour visiting every vertex exists, print the minimum possible maximum edge cost on the first line. If no such tour exists, print -1.

If a tour visiting every vertex exists, print on the next line the $N$ vertex numbers in the order they are visited, chosen so that the maximum edge cost is minimized. If several such tours exist, you may print any of them.