By an ingenious combination of warfare and arranged weddings, King Richard IV has gained control of a few remote areas of south-western Europe. (Actually, he is supposed to have coined the phrase that ‘marriage is the continuation of war by different means’.) To prot from his new property, deputies shall be installed at certain roads to collect toll fees from passing travellers. For each of the new areas, the royal cartographer has provided a simple map with the towns and major roads: Any two towns are connected by exactly one route (a sequence of roads from one town to another). To each road, the royal treasurer has assigned a number that indicates the prot he expects from collecting fees at that road. This number may be negative, which means that the cost of installing deputies is higher than the income. Your task is to determine a selection of roads that maximizes the total prot (the sum of the earnings of all selected roads). It is not required that every town is at the end of a selected road, but the selection has to be connected: It must be possible to go from any selected road to any other selected road by using only selected roads (this makes transporting the collected fees safer). Input The input consists of a sequence of simple maps. Each map starts with a line containing the number of roads n, where 1 ≤ n ≤ 100000. Each of the following n lines holds a road description that consists of three integer numbers a, b and p, where 1 ≤ a, b ≤ 200000 and −1000 ≤ p ≤ 1000. They indicate the towns a and b at the ends of the road and the prot p of selecting this road. Towns are identied by unique numbers and roads may be passed in both directions. The sequence of maps is followed by a line containing a ‘0’. Output For each map, output a line containing the maximum prot achievable by choosing a selection of roads as described above. Sample Input 4 1 2 -7 3 2 10 242 5 4 -2 3 1 2 -8 2 3 -8 3 4 -1000 5 14 15 0 15 92 10 92 65 -5 65 35 10 35 89 -30 0
2/2 Sample Output 12 0 15