Длины для дорог на ремонте

В области n городов с номерами от 0 до n - 1 и двусторонние дороги roads[i] = [a, b, w] между городами a и b. Если w > 0, это длина готовой дороги, и менять её нельзя. Если w = -1, дорога на ремонте и её длину предстоит назначить вам: целое число от 1 до 2·10⁹. Длина 2·10⁹ означает, что дорога по сути закрыта. Назначьте длины так, чтобы кратчайшее расстояние от города start до города finish стало ровно distance. Подходящих вариантов обычно много, поэтому нужен вполне определённый: 1. Возьмите наименьшее k ≥ 0, при котором цели можно добиться, держа закрытыми все ремонтируемые дороги, кроме первых k по порядку в списке. 2. Из этих k дорог первые k - 1 получают длину 1, а k-я — ту единственную длину, при которой расстояние становится ровно distance. Остальные ремонтируемые дороги получают 2·10⁹. Верните список всех дорог в исходном порядке, с уже назначенными длинами. Если добиться расстояния distance нельзя, верните пустой список.

n=4, roads=[[0, 1, -1], [1, 3, -1], [0, 2, 3], [2, 3, 4]], start=0, finish=3, distance=5 → [[0, 1, 1], [1, 3, 4], [0, 2, 3], [2, 3, 4]]

n=3, roads=[[0, 1, 2], [1, 2, -1], [0, 2, 3]], start=0, finish=2, distance=4 → []

n=3, roads=[[0, 1, -1], [1, 2, 6], [0, 2, 5]], start=0, finish=2, distance=5 → [[0, 1, 2000000000], [1, 2, 6], [0, 2, 5]]