Please justify your runtime and include a proof of correctness for your algorithm.

Suppose we are given a connected graph G=(V,E) with V=n,E=m. Each edge eE has a positive weight w(e)>0. Each vertex vV has a label av{1,2,,k}. Each label i{1,2,,k}, has a cost ci. t each vertex uV, you can perform two types of operations: 1. You can travel from u to some vertex v in its neighborhood, i.e. any v such that e=(u,v)E. The cost of this operation is w(e). 2. You can travel from u to some vertex v with the same label, i.e. any v such that au=av. The cost of this operation is cau. Given a source vertex s and a sink vertex t, design an O(X) algorithm that computes the minimal cost of traveling from s to t where O(X) is Dijkstra's shortest path algorithm runtime complexity on a graph with O(n) vertices and O(m) edges