You are given a weighted tree with nodes. The initial weight of the edge is , but every day the weight changes by . Thus, its weight will be in day . Note that the weights might be negative.
The diameter of is defined as a the maximum distance between any two nodes. Note that because the weights might be negative, it is possible the two nodes determining the diameter are not distinct.
You will observe the tree for days, starting from day 0 until day . You want to find a date which minimizes the diameter. Formally, you need to find an integer such that no other integer in yields a smaller diameter. If there is more than one such integer, you should find a smallest such integer.

The first line contains the number of nodes , and the number of observing days .
Each of the next  lines contains four integer , which indicates edge that connects two vertices  and , and it has cost  in day , and it changes by  everyday.

On the first line, print the integer  that minimizes the diameter in interval . If there is more than one such integer, find a smallest such integer.
On the next line, print the diameter of tree in day , when  is the day you found in first line.

5 5
1 2 20 -3
2 3 10 -3
3 4 22 -2
3 5 26 -3

5
23