Given a weighted undirected graph with N nodes and M edges (u, v, w) meaning node u and v is connected with weight w. 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

Constraints: N, M <= 2e5

a[i] < k <= 1e9

1 <= u, v, s, t <= n

w <= 1e9

Thanks