There is a maze containing N rooms numbered as (1,2,3,,N). There are M tunnels, each of which 6+3+6. connects two rooms. The tunnels allow going in one direction only. The energy required to pass through the tunnels is not same for every tunnel. Your goal is to start from room number 1 and exit through room number N wasting as minimum CO3 energy as possible. Assume there is an infinite supply of food in every room except the last room (N). Every time you visit a room you are allowed to eat a certain amount of food to gain some energy. The amount of energy you can gain from each room is different. i. Propose an efficient solution to find the path which requires minimum energy to exit the maze. ii. Give proper reasoning for choosing your solution. iii. Provide the algorithm for your solution and compute its worst runtime complexity. iv. Can the problem be solved if the tunnels allow movement in both directions? Justify your