Shortest Hamiltonian Path in a Weighted Graph

You are given an undirected weighted graph with (n) vertices labeled from (0) to (n-1). The task is to find the shortest Hamiltonian path from the starting vertex (0) to the destination vertex (n-1), where a Hamiltonian path is defined as a path that visits every vertex exactly once without repetition. The edge weight between two vertices (u) and (v) is denoted as (w). If there is no valid Hamiltonian path, output -1.

inputFormat

The input starts with two integers (n) and (m) on the first line, where (n) is the number of vertices and (m) is the number of edges. The following (m) lines each contain three integers (u), (v), and (w), indicating that there is an undirected edge between vertex (u) and vertex (v) with weight (w). It is guaranteed that vertices are numbered from (0) to (n-1).

outputFormat

Output a single integer representing the minimum total weight of a Hamiltonian path from vertex (0) to vertex (n-1) that visits every vertex exactly once. If such a path does not exist, output (-1).

sample

3 3
0 1 1
1 2 2
0 2 4

3