Кратчайший путь в отсутствие данного ребра

Предположим, что нам дан взвешенный граф G(V,E).

Граф содержит Nвершины (пронумерованы от 0 до N-1) и M двунаправленных ребер.

Каждое ребро(vi,vj)имеет положительное расстояние d (т. е. расстояние между двумя вершинами vivj равно d)

Существует не более одного ребра между любыми двумя вершинами , а также нет петли (т.е. ребро соединяет вершину с сама.)

Также нам дана Sисходная вершина и Dвершина назначения.

пусть Qбудет количеством запросов, каждый запрос содержит одно ребро e(x,y).

Для каждого запроса мы должны найти кратчайший путь от источника S до пункта назначения D, предполагая, что ребро (x,y) отсутствует в исходном графе. Если пути из S в D не существует, то нужно вывести число

Ограничения высокие 0<=(N,Q,M)<=25000

Как эффективно решить эту задачу?

До сих поря реализовал простой алгоритм Диякстры.

Для каждого запроса Q каждый раз, когда я присваиваю (x, y) бесконечности и нахождение кратчайшего пути Диджакстры.

Но этот подход будет очень медленным, так как общая сложность будет Q(временная сложность пути Диджастры Шортеса)*

Пример::

N=6,M=9
S=0 ,D=5

(u,v,cost(u,v))
0 2 4
3 5 8
3 4 1
2 3 1
0 1 1
4 5 1
2 4 5
1 2 1
1 3 3

Total Queries =6

Query edge=(0,1) Answer=7
Query edge=(0,2) Answer=5
Query edge=(1,3) Answer=5
Query edge=(2,3) Answer=6
Query edge=(4,5) Answer=11
Query edge=(3,4) Answer=8