Baahubali vs Bhallaladeva

4

1 votes
Ready, Graph, Flow, Approved, Easy-Medium
Problem

The kingdom of Mahishmathi is ruled by two brothers Baahubali and Bhallaladeva. Mahishmathi is a beautiful place which has N islands. Each island of the kingdom is connected at least one other island. A connection between one island to other island holds some importance to the kingdom. (Note: The connection are two ways.)

But since Bhallaladeva doesn't want to rule aside of Baahubali, he wants his share of kingdom. He takes this matter to his mother Sivagami. She gives the judgement as this, both the brothers can choose one island as their kingdom and the kingdom will be divided into two parts with each of the capitals in each part. The division of kingdom will be done such that minimum amount of importance is lost as it the people of kingdom doesn't have to suffer.

Sivagami approaches you to solve this problem. She has details of each connection of the kingdom and the capital islands Baahubali and Bhallaladeva chooses. Divide the kingdom into two as required.

Input Format:
First line has an integer N(number of connections in kingdom) and two characters X(capital of Baahubali) and Y(capital of Bhallaladeva).
Next N lines have three values ViVjIx which implies there is a connection from island Vi to island Vj with importance Ix.

Output Format:
Print a single integer - required answer to the question.

Constraints:

  • 1E50
  • 1Ix50
  • Vi,Vj,X,Z[A,Z]
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?