P3511 [POI 2010] MOS-Bridges

San Bytecisco is a beautifully situated coastal town. It consists of  small, yet densely populated islands, numbered from  to . Certain islands are connected with bridges, used for (bidirectional) road traffic. Each pair of islands can be connected with at most one bridge. The islands are connected in such a way that every island can be reached from every other by using the bridges only. Byteasar and Bytie are going for a bike trip in San Bytecisco. The will start their ride at the island no. 1. They intend to visit every island, while passing along every bridge once and ending the trip where it began, i.e., the island no. 1. Being quite seasoned riders, they expect some serious trouble from... the wind! After all, it is very windy along the coast, and especially so on the bridges between the islands. Obviously, depending on its speed and direction, the wind makes it hard to cross the bridge in different extent for either direction. For simplicity we will assume for every bridge and direction of crossing, the opposing wind speed is constant. Help Byteasar and Bytie to find a route as they desire that will in addition be the least tiresome. Byteasar and Bytie agreed on the maximum opposing wind speed as a measure of a route's tiresomeness.

无

无

$2 \le n \le 1000$，$1 \le m \le 2000$，$1 \le a_i,b_i \le n$，$a_i \neq b_i$，$1 \le l_i,p_i \le 1000$