Additionally, each node has a value a[i], and you can go from node i to node j with the cost of (a[i] + a[j]) % k, where k is a given constant. Find the shortest path from s to t

This is for all $$$n(n-1)/2$$$ pairs of vertices, meaning that the graph actually has $$$m + n(n-1)/2 = O(n^2)$$$ edges. Dijkstra runs in $$$O(E \log V)$$$ which is not fast enough if $$$E = O(V^2)$$$ and $$$V = 200\ 000$$$.