I have a weighted undirected graph with N veritces and M edges. Each edge has its weight and colour. There are at most 10 different colours in the whole graph. Each time I pass edges of different colour I have to pay additional fee equal to K. Given two vertices A and B, I want to find the shortest path between them. For example, given multigraph with 3 vertices, K = 5, and 3 edges: (1 -> 2 of weight 3 and colour 1), (1 -> 2 of weight 5 and colour 2), (2 -> 3 of weight 2 and colour 2), weight of the shortest path is 12. I would like to design an algorithm that would solve this problem in considerable time. My first idea was to use Dijkstra algorithm and for every vertex store an information about the edge from which I went into that vertex, but that strategy won't work for the example given above. So I don't have any other idea than brute-force algorithm.

Constraints:

N <= 10^5

M <= 10^5

K <= 10^5