Problem: Given a weighted graph G, source node, destination node and a value X. find the shortest route from source to destination.

If there is a path from U to V with cost C, and you choose the path the value of X will change to X=gcd(X,C). So if the new X is less than the cost of next edge you can't pick the next edge. This way you have to find out the shortest path possible.

Node and Edges size can be up to 10^5 and the time limit is 5s. What's the idea to solve this problem??

For better understanding you can find the problem statement Here (Problem F)