D. Hiking
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Professor Oak and Darío have taken advantage of their stay in Galicia to visit some points of interest. There are a total of $$$n$$$ points of interest and $$$m$$$ bidirectional trails connecting pairs of points.

Professor Oak is somewhat older now; he is worried about his knee and prefers to avoid climbing hills. Darío, on the other hand, is more concerned about not getting too tired before the OIE; therefore, he wants to minimize the difficulty of the trails he travels. The $$$i$$$-th point of interest is located at an elevation of $$$i$$$; moving from point $$$i_1$$$ to another $$$i_2$$$ with $$$i_1 \lt i_2$$$ is considered climbing a hill, regardless of which trail is used. Traveling the $$$j$$$-th trail causes $$$b_j$$$ units of fatigue for Darío. Sometimes, Darío catches his breath on trails that are easy to traverse; thus, $$$b_j$$$ can be a negative number.

They are currently at the hotel, the first point of interest, and want to reach the $$$n$$$-th point of interest. To do this, they want to find a path that minimizes the number of hills they have to climb and, in case of a tie, minimizes Darío's total fatigue. Can you help them find it?

Input

The first line of the input contains the number of cases $$$T$$$.

For each case, there will be a line of input with two integers $$$n$$$ and $$$m$$$, the number of points of interest and the number of trails between points of interest, respectively.

The following $$$m$$$ lines contain 3 integers $$$u_j$$$, $$$v_j$$$, and $$$b_j$$$, which represent the trail that connects the $$$u_j$$$-th and $$$v_j$$$-th points of interest and generates a fatigue of $$$b_j$$$.

Output

For each case, two integers should be printed on one line, $$$c$$$ and $$$s$$$, the minimum number of times they will have to climb a hill and the total fatigue of the path.

Scoring
  1. (11 points) For every $$$i$$$, the $$$i$$$-th point of interest is connected only to the $$$(i+1)$$$-th and $$$(i-1)$$$-th points of interest, except for points $$$1$$$ and $$$n$$$, which are only connected to the second point of interest and the $$$(n-1)$$$-th point, respectively.
  2. (28 points) The sum of $$$n$$$ and the sum of $$$m$$$ across all cases is at most $$$1000$$$.
  3. (31 points) It is guaranteed that the number of hills on the optimal path is at most $$$2$$$.
  4. (30 points) No additional restrictions.
Example
Input
2
3 2
1 2 -3
2 3 2
3 3
1 2 -3
2 3 2
1 3 20
Output
2 -1
1 20
Note

$$$1 \le T \le 10^5$$$.

$$$2 \le n, m \le 2 \cdot 10^5$$$.

The sum of $$$n$$$ and the sum of $$$m$$$ for all cases is at most $$$2 \cdot 10^5$$$.

$$$1 \le u_j, v_j \le n$$$.

$$$-10^{11} \le b_j \le 10^{11}$$$.

There is at least one path between each point of interest, $$$u_j \neq v_j$$$ for all $$$j$$$, and there is no more than one trail between two points of interest.