URI Online Judge | 2127

Vine System

By XI Maratona de Programação IME-USP, 2007 BR Brazil

Timelimit: 2

Researchers of the department of operational research from the University of British Columbia were hired to perform a weird task. Many countries from Africa decided to unite and use officially the means of transportation that became worldly known in the Tarzan movies: the vine. There are millions of vines in Africa and it is surprising the speed and efficiency that a person can move through the woods using this means of transportation. There was only one problem. Three big tribes dominate the vines: the makeleles, the maouhdas and the abedis. The tribes demand payment for vine used in transportation. Because the tribes still do not know the meaning of words like cartel, each one made its price, and they were very different from each other. While the makeleles were charging 1235 bongos by vine used, the malouhdas were charging 8977 and the abedis 10923 (Jane is still alive and helped intermediate the negotiation for this tribe).

The researchers were hired to choose the vines that will be part of the first vine system of the world. The people hiring built millions of "vine's stop" through the African woods and they wish that the vines were chosen in a way that it is possible to go to any point to another using the hired vines (you may have to change vines sometimes, as Tarzan did). You must say the cost of a system that meets all of these requirements and it is the cheapest possible.

You can assume that there are enough vines in the woods so that there is always a vine system that meets the requirements.

Input

The input contains several instances. The first line of each instance cointains two integers N (1 ≤ N ≤ 1000) and M (1 ≤ M ≤ 2000000), where N is the number of "vine's stop" and M is the number of vines. Each of the next M lines contains three integers U, V and C indicating that there is a vines that goes from U to V with a cost C, where 1 ≤ U, VN and C ∈ {1235,8977,10923}. The input ends with an end of file.

Output

For each instance, you must print an identifier "Instancia K", where K is the number of the current instance. On the next line print the cost of a system that meets the requirements described above.

After each instance, print a blank line

Sample Input Sample Output

3 3
1 2 10923
1 3 1235
2 3 1235
3 2
1 2 1235
2 3 10923

Instancia 1
2470

Instancia 2
12158