> Darth Vader: "Obi-Wan never told you what happened to your father."
>
> Luke Skywalker: "He told me enough! He told me you killed him!"
>
> Darth Vader: "No, I am your father."
>
> — Vader and Luke, on Cloud City
A list of n force-aware males numbered 1 through n were found. They are the chosen ones that will bring balance to the force. Being listed at the first place, Anakin Skywalker is the ancestor of all rest n−1 persons.
Interestingly, everyone else claims he is the father of some others, causing serious troubles. Fortunately, you found the list also comes with these claims and their likelihood. Your task is to find the true father of Nikana, the last one in the list (numbered n).
There are m claims in the list. The i-th claim consists of three integers: xi, yi, and wi, indicating that the xi-th person claims he is the father of the yi-th person, with a likelihood of wi.
Your task is to find a global assignment that assigns each person (except Anakin Skywalker) to someone in the list, i.e., find f(u) such that:
1. Everyone is assigned a father, i.e., f(u)∈{1,2,…,n} for all u∈{2,3,…,n}.
2. Each one's assigned father claims their relationship, i.e., for all u, there exists a claim i in the claims such that f(u)=xi∧u=yi.
3. Nobody is an ancestor of himself in the assignment, directly or indirectly.
4. The assignment maximizes the sum of the likelihood of the father-and-son relationships, i.e., W=∑iwi if f(u)=xi∧u=yi is in the assignment.
You should find the father of Nikana (the person numbered n) in such an optimized assignment. If multiple assignments have the same optimal likelihood W, you should find the assignment that minimizes the lexical number of his father, i.e., minimizes f(n) at the same time has an optimal assignment likelihood W. That makes Nikana closer to Anakin Skywalker.
>
> Luke Skywalker: "He told me enough! He told me you killed him!"
>
> Darth Vader: "No, I am your father."
>
> — Vader and Luke, on Cloud City
A list of n force-aware males numbered 1 through n were found. They are the chosen ones that will bring balance to the force. Being listed at the first place, Anakin Skywalker is the ancestor of all rest n−1 persons.
Interestingly, everyone else claims he is the father of some others, causing serious troubles. Fortunately, you found the list also comes with these claims and their likelihood. Your task is to find the true father of Nikana, the last one in the list (numbered n).
There are m claims in the list. The i-th claim consists of three integers: xi, yi, and wi, indicating that the xi-th person claims he is the father of the yi-th person, with a likelihood of wi.
Your task is to find a global assignment that assigns each person (except Anakin Skywalker) to someone in the list, i.e., find f(u) such that:
1. Everyone is assigned a father, i.e., f(u)∈{1,2,…,n} for all u∈{2,3,…,n}.
2. Each one's assigned father claims their relationship, i.e., for all u, there exists a claim i in the claims such that f(u)=xi∧u=yi.
3. Nobody is an ancestor of himself in the assignment, directly or indirectly.
4. The assignment maximizes the sum of the likelihood of the father-and-son relationships, i.e., W=∑iwi if f(u)=xi∧u=yi is in the assignment.
You should find the father of Nikana (the person numbered n) in such an optimized assignment. If multiple assignments have the same optimal likelihood W, you should find the assignment that minimizes the lexical number of his father, i.e., minimizes f(n) at the same time has an optimal assignment likelihood W. That makes Nikana closer to Anakin Skywalker.
