Problem In Short:
Given two nodes s and t in a weighted graph and Q queries to handle.
For every query you are given an edge to remove from the graph and you have to compute the shortest path between s and t.
Queries are independent, that is after you handle one query, reinsert the edge for subsequent queries.
N <= 7000, M <= 50000, Q <= 10000
(Please provide some hints, I'm unable to think a better solution than O(NM log N))