URI Online Judge | 2121

Tourism in Yekaterinburg

By XVII Maratona de Programação IME-USP, 2013 BR Brazil

Timelimit: 1

Many may think: "What will I do in Yekaterinburg? This town is at the end of the world! ". However, many interesting things happened in the city, having several monuments and historical sites. To name a few, Yekaterinburg has a monument that is a great computer keyboard located on the edge of the river Izet; a monument to Michael Jackson (!); in the Ipatiev mansion were murdered in the Romanovs (Tsar Nicholas, his wife, four daughters and son); there was a leak of anthrax in 1979; American U2 pilot was captured and condemned for espionage; among others. I.e., there is much work to do in the days when the city is visited.

The tourism center of Yekaterinburg constructed a map with the major tourist attractions as well as beautiful walks linking these paths. This map also shows a level of difficulty of each ride (related to duration, paving the way, relief etc..) And the direction in which it should be done. They wanted to build a route that passed by all the tourist attractions and rides. Was then devised a contest aimed at doing this route and at the same time paid homage to one of the sister cities of Yekaterinburg: Kaliningrad, whose name until the end of World War II was Königsberg. The idea was to build a route that would break one of the attractions, and going through all the rides if he returned to the starting point. We know that as in the case of Konigsberg bridges, it is not always possible to build a route as well. Therefore the central allowed, if necessary, the rides could be made more than once. However, she demanded that the overall difficulty of the route (sum of difficulty of each ride multiplied by the number of times it is done) was minimal. Thus, the contest consisted of proposing, from an initial route, which tours would be traversed more than once and how many times to obtain a route as desired by the center.


The input is composed of several instances and ends with the end of file (EOF).

The first line of each instance contains two integers N (2 ≤ N ≤ 50) and M (0 ≤ M N2+103), the number of city attractions and the number of trips respectively. The next M lines contains three integers, ai, bi, di (1 ≤ ai, biN) indicating that walking i get on there, finish in bi and has difficulty di (1 ≤ di ≤ 3x104).


For each instance print the minimum total difficulty of the desired route. If unable to obtain a route the way you want, print “impossivel”.

Sample Input Sample Output

2 2
1 2 10000
2 1 30000
4 7
1 2 1
2 1 2
2 3 4
2 3 4
3 2 3
3 4 10
4 3 100
3 2
1 2 1000
2 3 1000