Hello, codeforces!

Recently I came across a very interesting problem (and unfortunately I couldn't come up with an optimal solution): You are given an undirected graph with N <= 10^5 vertices and M <= 2*10^5 edges. Each edge has a color c_i <= 10^6. You need to find the minimum cost of the path from vertex 1 to vertex N, and the cost of the path is calculated as follows: the colors of the edges in the path are written in turn, and then the number of subsegments with the same colors is counted. Example: N=4, M=4, edges: 1<->2 with color 1, 2<->3 with color 2, 3<->4 with color 1, edge 1<->3 with color 1.

If we go the way 1->2->3->4, then the final price will be 2, because we will write out the colors of the edges: 1,2,1,1, and there will be 3 subsegments where the colors are the same: [1; 1], [2; 2], [3; 4]. But if we go the way 1->3->4, then the price will be 1, because all edges in the path have color 1.

Please help me with this problem and thanks in advance!