You are given a weighted directed graph with nodes and edges. Node 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:
Now you want to maximize the number of nodes such that the shortest path from source to those nodes are undefined and you have to do it at the minimum number of operations.
In the first line you are given an integer , the number of test cases. In the first line of each test case there are three integers and . Next lines each contains three space separated integers which denotes that there is a directed edge from node to node with weight .
Sum of over all test cases does not exceed and sum of over all test cases does not exceed .
Note: There could be multiple edges but no self loops.
For each test case, print two space separated integers, maximum possible number of nodes such that the shortest path from to them are undefined and the minimum number of operations required to do that respectively.
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
0% Solution Ratio
Login to submit