I am your Father!

Problem Description

Darth Vader: "Obi-Wan never told you what happened to your father."

Luke Skywalker: "He told me enough! He told me you killed him!"

Darth Vader: "No, I am your father."

¡ª Vader and Luke, on Cloud City A list of $n$ force-aware males numbered $1$ through $n$ were found. They are the chosen ones that will bring balance to the force. Being listed at the first place, Anakin Skywalker is the ancestor of all rest $n-1$ persons. Interestingly, everyone else claims he is the father of some others, causing serious troubles. Fortunately, you found the list also comes with these claims and their likelihood. Your task is to find the true father of Nikana, the last one in the list (numbered $n$). There are $m$ claims in the list. The $i$-th claim consists of three integers: $x_i$, $y_i$, and $w_i$, indicating that the $x_i$-th person claims he is the father of the $y_i$-th person, with a likelihood of $w_i$. Your task is to find a global assignment that assigns each person (except Anakin Skywalker) to someone in the list, i.e., find $f(u)$ such that:

1. Everyone is assigned a father, i.e., $f(u)\in\{1,2,\ldots,n\}$ for all $u\in\{2,3,\ldots,n\}$.
2. Each one's assigned father claims their relationship, i.e., for all $u$, there exists a claim $i$ in the claims such that $f(u) = x_i\land u=y_i$.
3. Nobody is an ancestor of himself in the assignment, directly or indirectly.
4. The assignment maximizes the sum of the likelihood of the father-and-son relationships, i.e., $W=\sum_{i} w_i$ if $f(u)=x_i\land u=y_i$ is in the assignment. You should find the father of Nikana (the person numbered $n$) in such an optimized assignment. If multiple assignments have the same optimal likelihood $W$, you should find the assignment that minimizes the lexical number of his father, i.e., minimizes $f(n)$ at the same time has an optimal assignment likelihood $W$. That makes Nikana closer to Anakin Skywalker.

Input

There are multiple test cases in the input file. The first line of the input gives the number of test cases $T$, then followed by $T$ test cases. The first line of a test case contains $n$ ($1\le n\le 10^3$) and $m$ ($m\le 10^4$), the number of persons and the number of claims, respectively. Then $m$ lines follows. The $i$-th line contains three integers: $x_i$, $y_i$, and $w_i$ indicating the claimed father, son, and likelihood. $1\le w_i\le 100$ is guaranteed. Nobody will claim someone as his son twice.

Output

For each test case, output one line containing two space-separated integers, the maximum likelihood $W$ and the father of Nikana.

Sample Input

2

3 3

1 2 10

1 3 10

2 3 10

3 3

1 2 10

1 3 10

2 3 11

Sample Output

20 1

21 2

Source

2017 Multi-University Training Contest - Team 8

https://acm.hdu.edu.cn/showproblem.php?pid=6141