Prime-Constrained Shortest Path

You are given an undirected weighted graph with n nodes and m edges. Each edge has an associated positive distance. Your task is to find the shortest path from node 1 to node n under the following constraint:

A move from a current node along an edge with distance d is allowed if and only if the sum of the current path length and d is a prime number. In other words, if at some point the accumulated distance is L, you can travel an edge of length d only if $$L + d$$ is a prime number. If no valid path exists that reaches node n, output -1.

Note: The graph is undirected, so each edge can be traversed in both directions.

inputFormat

The first line of input contains two integers n and m — the number of nodes and edges, respectively.

Then follow m lines, each containing three integers u, v, and d indicating that there is an edge between node u and node v with distance d.

outputFormat

Output a single integer: the length of the shortest valid path from node 1 to node n that satisfies the prime sum condition for each move. If no such path exists, output -1.

5 5
1 2 4
2 3 6
3 5 8
1 4 10
4 5 12

-1