Woburn Challenge 2017-18 Finals Round - Senior Division

The Party of Extraterrestrial Gangsters has begun its invasion of Earth! Vast armies of PEG soldiers have been deployed down to the surface throughout Scarberia, and the cows and monkeys have engaged them in battle.

Amidst the fighting, however, the aliens have also transported something else to the planet's surface — a bomb with devastating nuclear power! All life in Scarberia, and perhaps the rest of Earth, would surely cease if the bomb were to detonate. Fortunately, the PEG leaders are honourable enough to give their enemies a fighting chance. As such, they've set the bomb to go off after a period of three hours, and implanted a system for defusing it. They've even included an instruction manual along with it!

On the surface of the bomb, there are $N$ $(1\le N\le 200)$ electrical terminals. There are also $N-1$ wires running amongst the terminals, the $i$-th of which runs between terminals $A_i$ and $B_i$ $(1\le A_i,B_i\le N)$, and is either black (if $C_i=0$), or is otherwise white (if $C_i=1$). The wires have been arranged such that all pairs of terminals are reachable from one another by following a sequence of wires.

Bo Vine and the Head-Monkey have gotten their hands on the bomb and its accompanying instruction manual. According to the manual, the bomb will turn itself off if the following conditions are all met:

1. Each terminal $i$ receives an electrical current with some voltage $V_i$, such that $V_i$ is a positive integer.
2. For each black wire $i$ (such that $C_i=0$), the greatest common divisor (GCD) of $V_{A_i}$ and $V_{B_i}$ is equal to $1$.
3. For each white wire $i$ (such that $C_i=1$), the GCD of $V_{A_i}$ and $V_{B_i}$ is greater than $1$.

Bo Vine has ordered his cow engineers to prepare the necessary electrical equipment as quickly as possible. Meanwhile, the Head-Monkey has personally taken it upon herself to come up with a set of voltages $V_{1\dots N}$ which will successfully satisfy the conditions to defuse the bomb. However, having realized that PEG is essentially mocking them by dispatching a bomb which may be defused so easily, she's decided to get back at them by demonstrating the monkeys' superior intelligence and successfully defusing the bomb using as little voltage as possible. Help the Head-Monkey determine the minimum possible total voltage (sum of $V_{1\dots N}$ values) required to get the job done. Just make sure to figure it out within three hours!

Subtasks

In test cases worth $3/17$ of the points, $C_1=C_2=\cdots =C_{N-1}$.

Input Specification

The first line of input consists of a single integer, $N$.
$N-1$ lines follow, the $i$-th of which consists of three space-separated integers, $A_i$, $B_i$, and $C_i$, for $i=1\dots (N-1)$.

Output Specification

Output a single integer, the minimum possible total voltage required to defuse the bomb.

Sample Input

7
4 1 1
4 5 0
7 6 1
3 6 1
1 7 0
2 4 1

Sample Output

16

Sample Explanation

It's optimal to send

• a $1$-volt current to terminal $5$;
• $2$-volt currents to terminals $1$, $2$, and $4$; and
• $3$-volt currents to terminals $3$, $6$, and $7$.