Time Limit: 1000 mSec
Memory Limit: 32768 KB
Microhard company has just invented a brandly new speeding up device called Bright Network Hub(BNH). The BNH can be installed on the fibers between two nodes. When a BNH works, all the information going through this fiber will cost half of the original time. If n BNHs are installed on the same fiber, the speed for going through this fiber will be 2^n times faster.
In order to improve the speed of campus network, students in FZU are planning to buy some BNHs. Since they don't have enough money, they can only afford to buy m BNHs. Given the network of n nodes, you are to install these m BNHs on the proper lines, so that the time needed from node 1 to node n can be minimized.
In the above network the minimal time needed from 1 to 5 is 44ms. Now if you have 2 BNHs. Installing both of them on the fiber 1-2, the time from 1 to 2 will become 8.5ms. However, the optimal scheme is to install them on 1-3 and 3-5.