graphs – Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three

Question: Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three in a graph with natural weights of the edges.

My instructor has given me a hint of doing calculations modulo three and creating a new graph and applying Dijkstra’s algorithm on it.

I have no idea how to solve this question and I would be happy to get your help.

Thank you