Prime-Weighted Shortest Path

You are given an undirected graph with \(N\) nodes and \(M\) edges. Each edge is associated with a weight \(w\). Your task is to determine the minimum number of edges required to travel from node 1 to node \(N\) considering only those edges whose weight is a prime number. A number \(p\) is prime if it is greater than 1 and its only divisors are 1 and \(p\). If there is no valid path from node 1 to node \(N\) using only prime weighted edges, output \(-1\).

Note: The graph is undirected and may contain multiple test cases. Use an efficient algorithm (such as Breadth First Search) to solve the problem.

inputFormat

The first line contains a single integer \(T\) representing the number of test cases.

For each test case, the first line contains two integers \(N\) and \(M\) separated by a space, where \(N\) is the number of nodes and \(M\) is the number of edges.

This is followed by \(M\) lines, each containing three integers \(u\), \(v\), and \(w\) separated by spaces, indicating an undirected edge between node \(u\) and node \(v\) with weight \(w\).

outputFormat

For each test case, output a single integer on a new line which is the minimum number of edges required to go from node 1 to node \(N\) using only edges that have prime weights. If no such path exists, output \(-1\).

2
5 5
1 2 3
1 3 4
2 4 5
3 5 7
4 5 11
3 3
1 2 6
2 3 17
1 3 20

3
-1