2009 World Finals hosted by Kth CPC 2009 以acm International Collegiate Programming Contest Problem e Fare and balanced Input fare in landling traffic congestion is a difficult challenge for young urban planners. Millions of drivers, each with different goals and each making independent choices, combine to form a complex system with sometimes predictable, sometimes chaotic behavior. As a devoted civil servant, you have been tasked with optimizing rush hour traffic over collections of roads All the roads lie between a residential area and a downtown business district. In the morning, each person living in the residential area drives a route to the business district. The morning commuter traffic on any particular road travels in only one direction, and no route has cycles(morning drivers do not backtrack) Each road takes a certain time to drive, so some routes are faster than others. Drivers are much more likely to choose the faster routes, leading to congestion on those roads. In order to balance the traffic as much as possible you are to add tolls to some roads so that the perceived"cost" of every route ends up the same. However, to avoid annoying drivers too much, you must not levy a toll on any driver twice, no matter which route he or she Figure 5 shows a collection of five roads that form routes from the residential area(at intersection 1)to the downtown business district(at intersection 4). The driving cost of each road is written in large blue font. The dotted arrows show the three possible routes from 1 to 4. Initially the costs of the routes are 10, 8 and 12. After adding a toll of cost 2 to the road connecting I and 4 and a toll of cost 4 to the road connecting 3 and 4, the cost of each route becomes 12 10+2=12 10+2 5+3+4=12 3+4 z 2) Figure 5: Roads connecting residential area at intersection 1 to business district at intersection 4 You must determine which roads should have tolls and how much each toll should be so that every route from start to finish has the same cost(driving time cost possible toll)and no route contains more than one toll road Additionally, the tolls should be chosen so as to minimize the final cost. In some settings, it might be impossible to impose tolls that satisfy the above conditions Input consists of several test cases. A test case starts with a line containing an integer N(2SN<50000), whicl is the number of road intersections, and r(I srs50000), which is the number of roads. Each of the next R lines contains three integers xh, yi, and c (Isx,ysN,IsCs1000), indicating that morning traffic takes road i from intersection x, to intersection y with a base driving time cost of cp. Intersection I is the starting residentialProblem E Fare and Balanced Input: fare.in Handling traffic congestion is a difficult challenge for young urban planners. Millions of drivers, each with different goals and each making independent choices, combine to form a complex system with sometimes predictable, sometimes chaotic behavior. As a devoted civil servant, you have been tasked with optimizing rush￾hour traffic over collections of roads. All the roads lie between a residential area and a downtown business district. In the morning, each person living in the residential area drives a route to the business district. The morning commuter traffic on any particular road travels in only one direction, and no route has cycles (morning drivers do not backtrack). Each road takes a certain time to drive, so some routes are faster than others. Drivers are much more likely to choose the faster routes, leading to congestion on those roads. In order to balance the traffic as much as possible, you are to add tolls to some roads so that the perceived “cost” of every route ends up the same. However, to avoid annoying drivers too much, you must not levy a toll on any driver twice, no matter which route he or she takes. Figure 5 shows a collection of five roads that form routes from the residential area (at intersection 1) to the downtown business district (at intersection 4). The driving cost of each road is written in large blue font. The dotted arrows show the three possible routes from 1 to 4. Initially the costs of the routes are 10, 8 and 12. After adding a toll of cost 2 to the road connecting 1 and 4 and a toll of cost 4 to the road connecting 3 and 4, the cost of each route becomes 12. Figure 5: Roads connecting residential area at intersection 1 to business district at intersection 4 You must determine which roads should have tolls and how much each toll should be so that every route from start to finish has the same cost (driving time cost + possible toll) and no route contains more than one toll road. Additionally, the tolls should be chosen so as to minimize the final cost. In some settings, it might be impossible to impose tolls that satisfy the above conditions. Input Input consists of several test cases. A test case starts with a line containing an integer N (2 ≤ N ≤ 50000), which is the number of road intersections, and R (1 ≤ R ≤ 50000), which is the number of roads. Each of the next R lines contains three integers xi, yi, and ci (1 ≤ xi, yi ≤ N, 1 ≤ ci ≤ 1000), indicating that morning traffic takes road i from intersection xi to intersection yi with a base driving time cost of ci. Intersection 1 is the starting residential