You are given a weighted directed graph with $n$ nodes and $m$ edges. Node $S$ is marked as the source node and each edge has a positive weight. So the shortest path from source to each node is defined(shortest path to nodes which are not reachable from the source node is also considered defined and cost of shortest path to those nodes is infinity). But you want to make it undefined.
Shortest path from one node to another is undefined if you can make the cost of the shortest path arbitrarily small.
To do that you can do the following operation any number of times:
- Choose any edge and decrease its weight by
$1$.
Now you want to maximize the number of nodes such that the shortest path from source $S$ to those nodes are undefined and you have to do it at the minimum number of operations.
Input
In the first line you are given an integer $T (1 ≤ T ≤ 10)$, the number of test cases. In the first line of each test case there are three integers $n (1 ≤ n ≤ 1000), m (0 ≤ m ≤ 5000)$ and $S (1 ≤ S ≤ n)$. Next $m$ lines each contains three space separated integers $u$ $v$ $c$ $(1 ≤ u,v ≤ n, u ≠ v, 1 ≤ c ≤ 10^{9})$ which denotes that there is a directed edge from node $u$ to node $v$ with weight $c$.
Sum of $n$ over all test cases does not exceed $5000$ and sum of $m$ over all test cases does not exceed $25000$.
Note: There could be multiple edges but no self loops.
Output
Print $T$ lines.
For each test case, print two space separated integers, maximum possible number of nodes such that the shortest path from $S$ to them are undefined and the minimum number of operations required to do that respectively.
Sample
| Input | Output |
|---|---|
2 3 3 1 1 2 4 2 1 5 2 3 3 4 5 1 1 2 5 1 3 5 3 4 3 4 3 3 3 2 1 | 3 10 3 7 |
