Посчитаем длины кратчайших путей $$$dist[u]$$$ в ситуации, если бы подсказки не было, с помощью алгоритма Дейкстры на наших m ребрах.

Далее хотим пересчитать через один прыжок с помощью подсказки. Рассмотрим вершину $$$u$$$. Из неё мы можем прыгнуть с помощью подсказки во все вершины, с которыми она не соединена. Заметим, что длина пути тогда будет всегда $$$dist[u] + c_u$$$. То есть чтобы пересчитать кратчайшие пути с помощью $$$u$$$ нужно сделать $$$min=$$$ с новым расстоянием для всех вершин, не смежных $$$u$$$. Заметим, что массив всех вершин разбивается на множество отрезков вершин, не смежных с нашей. Тогда мы должны сделать много раз $$$min=$$$ на отрезке.

Заметим, что всего по всем вершинам таких запросов на $$$min=$$$ на отрезке $$$O(m)$$$. Тогда достаточно сделать эти запросы в дереве отрезков, чтобы они суммарно работали за $$$O(m log n)$$$.

В конце запустим алгоритм Дейкстры еще раз на полученных расстояниях, так как после прыжка-подсказки можно дальше ходить по графу.