Shortest Path with an Even-Indexed Node

You are given an undirected weighted graph with n nodes and m edges. Your task is to find the shortest path from node 1 to node n such that the path includes at least one even-indexed node (i.e. a node whose index is divisible by 2).

If such a path exists, output its total weight. Otherwise, output -1.

Note: The graph is undirected, and the weights of the edges are positive integers. Node 1 is always the starting point, and node n is the destination. The starting node (node 1) is odd, so the path must include some other node with an even index.

The problem can be formulated using the following concept: Let \( dp[i][j] \) be the minimum distance to reach node \( i \) with \( j \) representing whether an even-indexed node has been visited (0: not visited, 1: visited). The answer is \( dp[n][1] \) if it exists, otherwise -1.

inputFormat

The first line contains two integers n and m (the number of nodes and edges respectively).

Each of the following m lines contains three integers u, v and w denoting an undirected edge between node u and node v with weight w.

Input is provided through standard input (stdin).

outputFormat

Output a single integer: the minimum total weight of a valid path from node 1 to node n that passes through at least one even-indexed node. If no such path exists, output -1. The output should be printed to standard output (stdout).

5 6
1 2 2
2 3 3
3 4 7
4 5 1
2 5 5
1 3 8

7