However, sending emails in the dark organization is not so easy. Networks are controlled by the firewalls. To protect the secret of APTX4869, A few firewall rules are set in the local area network.Bourbon wants to destroy the organization. He cracked into the LAN and want to download documents about APTX4869. He knows the rules of firewall, but he can't stop the firewall.There are n computers and m channels in the network. Files can be transferred only in the channels, whose rate is limited. For each channel i, 3 arguments. are set in the rules, which means the file transfer speed between computer. KB/s. Data transfer is bidirectional. Computers are also slow. For each computer i, only. KB data transfer can be done in one second. Network delay is not considered.Now Bourbon has controlled the k-th computer and started to download the document from computer 1. It is guaranteed that there is one channel connecting 1 and k. The size of this secret document is s KB. He wants to know how much time it takes at least to complete this mission. Now, this clever man, can you help Bourbon?
"Across the Great Wall, we can reach every corner in the world." This is the first e-mail sent from China. However, sending emails in the dark organization is not so easy. Networks are controlled by the firewalls. To protect the secret of APTX4869, A few firewall rules are set in the local area network. Bourbon wants to destroy the organization. He cracked into the LAN and want to download documents about APTX4869. He knows the rules of firewall, but he can't stop the firewall. There are n computers and m channels in the network. Files can be transferred only in the channels, whose rate is limited. For each channel i, 3 arguments u_i, v_i, w_i u i ,v i ,w i are set in the rules, which means the file transfer speed between computer u_i u i and v_i v i is w_i w i KB/s. Data transfer is bidirectional. Computers are also slow. For each computer i, only a_i a i KB data transfer can be done in one second. Network delay is not considered. Now Bourbon has controlled the k-th computer and started to download the document from computer 1. It is guaranteed that there is one channel connecting 1 and k. The size of this secret document is s KB. He wants to know how much time it takes at least to complete this mission. Now, this clever man, can you help Bourbon?
