Router Destination

Problem Statement

Router Destination Problem Description A network has N routers numbered 1 to N , joined by M bidirectional cables. A packet starts at router 1 carrying X units of energy. Cable i joins routers U and V . Crossing it in either direction drains E units of energy from the packet and takes T seconds. The packet may cross a cable only while it holds at least E units of energy. Every router owns an unlimited supply of energy boosters. While the packet sits at router i , that router may apply as many of its own boosters as it likes: each one raises the packet's energy by B[i] units and costs P[i] seconds. Only the router the packet is currently at may boost it. For every router R from 2 to N , report the smallest total number of seconds needed to bring the packet from router 1 to router R . The packet may pass through any router any number of times on the way. Input Format Line 1: three integers N , M and X . The next M lines: four integers U V E T , one cable each. The next N lines: two integ