Chef and Jerry

Chef has been working very hard all day and is now tired. He decides to play his favorite video game named J.E.R.R.Y. . In this game, Chef plays as the character J.E.R.R.Y who wants to eat the cheese located in the fridge. The game map can be represented as a graph with $N$ locations (numbered from $1$ to $N$) and $M$ bidirectional roads. You also know the time J.E.R.R.Y will take to travel ea