59E - Кратчайший путь

I can't find any way how to implement this problem. How can I mark the triplets and when I'll iterate over the node/edges to find Shortest Path how to ignore the all marking triplets? Please give me some suggestion.

Thanks!