I am stuck on this problem. https://www.codechef.com/problems/IOPC16K

Problem Statement:

Find out what will be the new shortest path if one of the edge on the original shortest path is removed.Find for all of the edges in shortest path path(Given Unique original shortest path).

Constraints:

no. of edges <= 1e5

no. of nodes <= 1e5

weights of edges <= 1e9

I Looked at some of the AC solutions but could not get the Idea. So if somebody can share the Idea to solve the problem it would be very Helpful! (I think its on some Algorithmic Paper).