Given a undirected weighted graph with a source node and a destination node. The task is to find the shortest path between them.

But, their is a condition for choosing a edge for each time. Initially a number is given, X. An adjacent node can be only be visited if (X >= weight to reach the adjacent node to the current node) and after reaching any adjacent node the value of X changes to X = GCD(X, weight of edge that used to reach the current node).

There can be 10^5 nodes in the graph. weight of each edge can be 10^5 as well.

Can anyone provide a solution idea? Thank you.

http://lightoj.com/volume_showproblem.php?problem=1093

I understood the problem but failed to understand the sample test cases.