IIT Guwahati has decided to construct a new hostel as it will be organizing the next Inter IIT. For the construction of the hostel, contractor needs one iron rod having minimum length whose ends have some specific color(s). But, it may happen that the set of rods the contractor has, do not contain that particular type of rod. So, he is using some adhesive to join the iron rods end-to-end, but, the joint is strong only if the rods are joined by the ends having same color.
So, you are given a set of iron rods of lengths L[i] (for the ith rod) and whose left and right ends are colored with colors a[i] and b[i]. Also all dimensions except length are same for all iron rods. You can join two iron rods by joining their ends having same color.
You are to construct an iron rod whose left and right ends are of a desired color A and B; if many such iron rods can be formed then construct the one with minimum length.
We will denote colors with positive integers.
Each iron rod is denoted by three integers L[i], a[i] and b[i]. a[i] and b[i] are colors of left and right ends of the ith rod. L[i] is its length.
INPUT:
First line contains three integers N, A, B (A and B are distinct)
N : number of iron rods
A,B : color of the two ends
Next N lines contain three integer each, a[i], b[i], L[i] as defined in problem statement.
OUTPUT:
If it is possible to form the iron rod with colors A, B then output the minimum length possible for iron rod. If it is not possible the output -1.
CONSTRAINTS:
1 <= N, a[i], b[i], A, B <= 100000
1 <= L[i] <= 1000000
PROBLEM SETTER: Amit Mittal