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

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

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

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