Unlimited Flight Cards

Kostas travels a lot. His job requires him to be in Paris this week, Sofia the next, then Beijing after two days, followed by Athens. Oh, I'm tired just telling you... Naturally, he spends a ton of money on plane tickets.

A few days ago, the airlines decided to issue unlimited flight cards (similar to unlimited bus route cards) for customers exactly like Kostas. With a slight difference, though. Instead of a single card for all possible flights (which would be quite expensive), they issue one card for each different flight, allowing cardholders to fly with that specific flight (in both directions) as many times as they want for a year. The cost of these cards varies according to the distance.

Kostas wants to be able to travel from any airport to any other, and he doesn't mind changing flights with intermediate stops to save money. Help him find which unlimited flight cards he needs to buy to achieve this with the minimum possible total cost.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that, after reading the available unlimited flight cards and their costs, calculates the minimum amount Kostas must pay to buy some of them, so he can travel from any airport to any other.

Input Files

The input files named uflights.in are text files with the following structure: The first line contains two integers, N and M, separated by a single space. The number N (1 ~\le~ Ν ~\le~ 100.000) corresponds to the number of airports, and the number M (1 ~\le~ Μ ~\le~ 1.000.000) corresponds to the number of available unlimited flight cards. Each of the next ~M~ lines contains three integers, A, B, and K, separated in pairs by a single space, describing an available unlimited flight card between airports A (1 ~\le~ Α ~\le~ Ν) and B (1 ~\le~ Β ~\le~ Ν), with a cost of K (1 ~\le~ Κ ~\le~ 100). Assume that airports are numbered from ~1~ to ~N~, and ~A \ne B~.

Output Files

The output files named uflights.out are text files with the following structure: They have exactly one line with an integer number: The minimum total cost for Kostas to be able to travel from any airport to any other.

Examples of Input - Output Files:

STDIN (uflights.in)

7 9
1 2 50
3 1 10
4 6 80
1 4 40
3 5 20
4 3 30
2 6 60
5 6 70
5 7 90

STDOUT (uflights.out)

260

Kostas can choose to buy the cards 1~\leftrightarrow~2, 3~\leftrightarrow~1, 3~\leftrightarrow~5, 4~\leftrightarrow~3, 2~\leftrightarrow~6, and 5~\leftrightarrow~7, with a total cost:

Thus, he can travel from any airport to any other. For example, if he needs to travel from airport 1 to airport 7, he can follow the route 1~\to~3~\to~5~\to~7. There is no cheaper option of cards with which he can achieve his goal.

Notes:

• Consider that there will be at least one valid combination of unlimited flight cards that will allow Kostas to travel from any airport to any other.
• Maximum Available Memory: 64 ΜΒ
• Maximum Execution Time: 3 sec