Minimum Cost Path in a Weighted Graph with Vertex Transition Cost

Given an undirected graph with \(n\) vertices and \(m\) edges, find the minimum cost to travel from vertex 1 to vertex \(n\).

The cost at each vertex is defined as follows:

• For the starting vertex 1, its cost is the weight of the edge used to leave it.
• For an intermediate vertex, the cost is \(\max(w_{in},w_{out})\), where \(w_{in}\) is the weight of the edge used to enter the vertex and \(w_{out}\) is the weight of the edge used to leave it.
• For the destination vertex \(n\), its cost is the weight of the edge used to enter it.

Thus, if the chosen path uses edges \(e_1, e_2, \ldots, e_k\) (where \(e_1\) is used to leave vertex 1 and \(e_k\) enters vertex \(n\)), then the total cost is computed as:

[ \text{TotalCost} = w(e_1) + \sum_{i=2}^{k-1} \max(w(e_{i-1}),w(e_i)) + w(e_k). ]

Output the minimum cost possible. If no path exists, output -1.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (2 \le n,\; m \ge 1)\) representing the number of vertices and edges.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\) indicating there is an undirected edge between vertices \(u\) and \(v\) with weight \(w\). All weights are positive integers.

outputFormat

Output a single integer representing the minimum cost from vertex 1 to vertex \(n\). If there is no valid path, output -1.

sample

4 4
1 2 3
2 3 4
3 4 5
1 4 10

17