Minimum Perimeter Region

Farmer Brown’s ranch has been partitioned by runaway fence segments. Each fence segment has a length between 1 and 200 feet and is uniquely numbered from 1 to N. Every fence has two endpoints. At each endpoint the fence is joined to exactly one other fence – that is, for each fence, you are given two numbers which indicate the labels of the other fences joining at its endpoints. (It is guaranteed that no fence is connected to itself.) These pairings indicate how the fences form a network that subdivides the ranch into several regions. Your task is to determine the perimeter of the region with the smallest total fence‐length.

In other words, if a region has a boundary composed of a set of fence segments, its perimeter is the sum of the lengths of those segments; you must output the minimum such sum over all regions created by the fence network.

Note that if a fence appears as an edge in a cycle (face boundary), the pairing at its endpoints is given. Any formula should be written in ( \LaTeX ) format. For example, if a fence has length ( l_i ), then the perimeter ( P ) of a cycle is ( P = \sum_{i \in \text{cycle}} l_i ).

inputFormat

The first line contains a single integer N (the number of fence segments). Each of the following N lines contains three integers: the length of the fence segment and two integers which represent the labels of the fence segments connected to its two endpoints, respectively.

It is guaranteed that for every fence i and for each endpoint, if the endpoint is connected to fence j then in fence j one of the endpoints is connected back to fence i. You may assume that a valid fence network (planar subdivision) is formed.

outputFormat

Output a single integer which is the minimum perimeter (i.e. the minimum total fence‐length) among all regions (cycles) formed by the fence network.

sample

3
100 2 3
200 3 1
150 1 2

450