Telecommunication Costs

A telecommunication company is trying to attract a new customer. The customer is interested in leasing optical fibers that connect ~N~ cities, denoted as ~a_1~, ~a_2~, ~...~, ~a_N~. The company needs to submit a proposal with the cost ~c_{ij}~ for the direct connection of each pair of cities ~a_i~ and ~a_j~, ~1 \le i~, ~j \le N~, where ~i \ne j~ Based on the proposal, the customer will select a spanning tree that covers all cities and ensures the minimum total connection cost.

The company has significant reasons to influence the customer's choice, leading them to choose a specific spanning tree ~T~ for connecting the cities. Given the cost of the connections included in ~T~, the company desires to adjust the cost of the remaining connections so that ~T~ emerges as the unique minimum spanning tree covering all cities. However, to avoid appearing too expensive to the customer, the company wants the proposed cost for the remaining connections to be calculated so that the total sum of the proposed costs for all city pairs is minimized.

Problem:

Develop a program in one of the IOI languages which, after reading the costs of the connections included in the spanning tree ~T~, calculates the minimum possible total proposed cost in the company's proposal so that ~T~ is the unique minimum spanning tree.

Input Files:

The input files, named telecom.in, are text files with the following structure: The first line contains an integer ~N\;(3 \le N \le 500.000)~, the number of cities. Cities are numbered from ~1~ to ~N~. Each of the next ~N - 1~ lines contains three positive integers ~i~, ~j~, and ~c_{ij}~, separated in pairs by a single space. These indicate that city ~a_i~ is directly connected to city ~a_j~ in the selected tree ~T~ with a cost of ~c_{ij}~. It holds true that ~1 \le i~, ~j \le N~, ~i \ne j~, and ~1 \le c_{ij} \le 12.000~.

Output Files:

The output files named telecom.out are text files with the following structure: They contain only one line with a single integer, the minimum total proposed cost for all city pairs, so that the selected tree ~T~ is the unique minimum spanning tree for cities ~a_1~, ~a_2~, ~...~, ~a_N~ based on the proposed costs.

Note: For large values of ~N~, the minimum total cost (and possibly some of the intermediate results needed for its calculation) may exceed ~2^{32}~.

Examples of Input - Output Files:

1st

STDIN (telecom.in)

3
1 2 4
2 3 7

STDOUT (telecom.out)

19

Explanation of the first example:

The selected tree has direct connections between cities ~1~ and ~2~, with a cost of ~4~, and between cities ~2~ and ~3~, with a cost of ~7~. For this to be the unique minimum spanning tree among cities ~1~, ~2~, and ~3~, the proposed cost for connecting cities ~1~ and ~3~ must be at least ~8~. Therefore, the minimum total proposed cost is equal to ~4 + 7 + 8 = 19~.

2nd

STDIN (telecom.in)

4
1 2 1
1 3 1
1 4 2

STDOUT (telecom.out)

12

Explanation of the second example:

The selected tree has direct connections between cities ~1~ and ~2~, with a cost of ~1~, between cities ~1~ and ~3~, with a cost of ~1~, and between cities ~1~ and ~4~, with a cost of ~2~. For this to be the unique minimum spanning tree among cities ~1~, ~2~, ~3~, and ~4~, the proposed cost for connecting cities ~2~ and ~3~ must be at least ~2~, for connecting cities ~2~ and ~4~, the cost must be at least ~3~, and for connecting cities ~3~ and ~4~, the cost must be at least ~3~. Therefore, the minimum total proposed cost is equal to ~1 + 1 + 2 + 2 + 3 + 3 = 12~.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.