You are the best friend of some girl. You always prevent someone from approaching your friend. On a Friday night, your friend is waiting for the bus to get away the campus. Unfortunately, someone heard about this. He wants to take the same bus to make a chance to chat with your friend. To save the world, you need to stop someone to get to the bus stop before the bus comes. “Dao Dan” is the Chinese pronunciation of the missile and also a name of the salesman who sells the missiles. You can buy ONLY ONE missile. And the power-k missile will destroy ALL roads whose stability is less than or equal to k. To make your friend safe and save the money, what is the minimum power of the missile you need to buy to archive the goal?
Each test case starts with a line containing three integers n(2<=n<=100000) ,m(1<=m<=200000) and t(0<=t<=109) indicating the number of locations on the map, the number of the roads, and the time that the bus “exactly” get away from the bus stop. Following this are m lines, each containing 4 integers representing the endpoints of the bi-directed road ui, vi (0<=ui,vi
Output the minimum power of the missile you need to buy. If you don’t need to buy the missile, output “Safe.”.