Привет, кодфорсес!

Недавно наткнулся на вот такую интересную задачу (и к сожалению не смог придумать оптимальное решение): Дается неориентированный граф из N <= 10^5 вершин и M <= 2*10^5 ребер. Каждое ребро имеет цвет c_i <= 10^6. Необходимо найти минимальную цену пути от вершины 1 до вершины N, причем цена пути рассчитывается следующим образом: поочередно выписываются цвета ребер в пути, а далее считается количество подотрезков с одинаковыми цветами. Пример: N=4, M=4, ребра: 1<->2 с цветом 1, 2<->3 с цветом 2, 3<->4 с цветом 1, ребро 1<->3 с цветом 1.

Если мы пойдем путем 1->2->3->4, то итоговая цена будет 2, т.к. мы выпишем цвета ребер: 1,2,1,1, и тут будет 3 подотрезка где цвета одинаковы: [1; 1], [2; 2], [3; 4]. Но если мы пойдем путем 1->3->4, то цена будет 1, т.к. у всех ребер на пути цвет 1.

Прошу помощи в решении данной задачи и заранее благодарю!