Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

No More Shortest Path

By tbs_sajal15 · Limits 3s, 512 MB

You are given a weighted directed graph with nn nodes and mm edges. Node SS 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 11.

Now you want to maximize the number of nodes such that the shortest path from source SS 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(1T10)T (1 ≤ T ≤ 10), the number of test cases. In the first line of each test case there are three integers n(1n1000),m(0m5000)n (1 ≤ n ≤ 1000), m (0 ≤ m ≤ 5000) and S(1Sn)S (1 ≤ S ≤ n). Next mm lines each contains three space separated integers uu vv cc (1u,vn,uv,1c109)(1 ≤ u,v ≤ n, u ≠ v, 1 ≤ c ≤ 10^{9}) which denotes that there is a directed edge from node uu to node vv with weight cc.
Sum of nn over all test cases does not exceed 50005000 and sum of mm over all test cases does not exceed 2500025000.
Note: There could be multiple edges but no self loops.

Output

Print TT lines.
For each test case, print two space separated integers, maximum possible number of nodes such that the shortest path from SS to them are undefined and the minimum number of operations required to do that respectively.

Sample

InputOutput
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

    Discussion

    Statistics


    0% Solution Ratio

    Submit

    Login to submit