Router Destination

Problem Statement

Router Destination Problem Description In a network, there are N routers numbered through 1 to N, connected by M cables. There is a packet at router 1 and initially, it has X units of energy. The i-th cable connects router Ui and router Vi bidirectionally, and when packet crosses this cable its energy gets attenuated by Ei energy units and it takes Ti seconds to cross. Packet can't cross the cable if it does not have enough energy. Each router has an infinite number of energy boosters and each router can use any number of energy boosters on the packet. If router Ri decides to use an energy booster on the packet, the packet's energy will increase by Bi units and this process will take Pi seconds for each energy booster. For each router R from 2 to N as destination, find the minimum time taken by the network to send the packet from router 1 to router R. Input Format First line of input contains three integers, N, M, and X representing the number of routers, number of connecting cables, a