Rafael Phofo was a happy guy living with his best friend, Danilo Gheyi. They were so friends that they made a blood pact during their childhood. But Matheus Pheverso, the owner of the Infelicity Forest, a forest that Rafael and Danilo used to cross every day, didn't like to see them together. He always tried to separate them; a day he finally achieved his goal, making the two guys lost in two different points of his forest.

Rafael Phofo knew it wouldn't be hard to find his friend, because he had some RS2D (love notes), the money that Matheus Pheverso charged to let his visitors cross each street connecting two points of the forest.

But there was a problem: analyzing the map of the forest, Rafael realized that his amount of RS2D could be insufficient. So he called you, a great programmer and also his friend, to know if it's possible to find Danilo with that amount of RS2D. You need to write a program that determine the minimum amount of RS2D necessary. Consider that Rafael is in the position 1 of the forest and Danilo is in the position N.

Input

The input consists of several instances; the first line contains an integer K (1 ≤ K ≤ 20), the amount of instances. The first line of each instance contains two integers N and M (1 ≤ N ≤ 10⁶, 1 ≤ M ≤ 10⁶), the amount of points and the amount of streets in the forest, respectively. The next M lines contain three integers A, B and C (1 ≤ A ≤ N, 1 ≤ B ≤ N, 1 ≤ C ≤ 10⁶), indicating a one-way street from point A to point B with cost C.

Output

For each instance output a sentence “Rafael will find his love for P RS2D.”, and P represents the minimum amount of RS2D that Rafael needs to caught Danilo.

Example

Input:
2
6 9
1 2 7
1 5 14
1 3 9
2 4 15
2 3 10
3 5 2
3 4 11
5 6 9
4 6 6
5 7
1 2 1
1 3 5
2 4 2
3 4 2
3 5 3
2 5 3
4 5 1

Output:
Rafael will find his love for 20 RS2D.
Rafael will find his love for 4 RS2D.