Shortest Pilgrimage

A pilgrim keeps making a pilgrimage that seems like it will never end. There are $N$ holy sites on the earth, numbered from 1 to $N$. There are $M$ roads, and road $i$ lets you travel between sites $x\_i$ and $y\_i$ in $w\_i$ minutes.

The pilgrim plans a new pilgrimage that starts at site 1 and ends at site $N$. The pilgrimage visits exactly eight different sites, including sites 1 and $N$. No site may be visited more than once.

Considering only the travel time on the roads, find the shortest time the pilgrimage takes.

The first line contains the number of sites $N$ and the number of roads $M$.

Each of the next $M$ lines contains road $i$ as $x\_i$, $y\_i$, $w\_i$ ($1 \leq x\_i,y\_i \leq N$, $x\_i \neq y\_i$, $1 \leq w\_i \leq 10^8$). The same pair of sites is never connected by more than one road.

Print the shortest time of the pilgrimage in minutes on the first line. If no pilgrimage satisfies the conditions, print -1.