Будучи членом жюри конкурса "Лучший архитектурный конкурс", Вам поручено вычислить надежность системы. Все системы, включенные в конкурс, состоят из ряда компонент, зависящих друг от друга. Надежность такой системы зависит от ущерба, нанесенного неисправным компонентом. В идеале неисправный компонент не должен иметь никаких последствий, но поскольку большинство компонентов зависят друг от друга, некоторые другие компоненты также обычно ломаются.

Большинство компонентов являются устойчивыми к коротким отказам компонентов, от которых они зависят. Например, база данных может быть недоступна за минуту до истечения срока действия кэша, а новые данные должны быть получены из базы данных. В этом случае кэши могут выжить в течение минуты после сбоя базы данных, прежде чем сами придут в негодность. Если компонент зависит от других компонентов, которые выходят из строя, то он также выйдет из строя. Кроме того, компонент не зависит напрямую от себя, однако возможна косвенная самозависимость через другие компоненты.

Вы хотите знать, сколько компонентов потерпит неудачу, если какой-то компонент сломается, и сколько времени пройдет до того, как все компоненты, которые в конечном итоге потерпят неудачу, действительно придут в негодность. Это сложно рассчитать вручную, поэтому Вы решили написать программу, которая поможет Вам. По описанию системы и исходному сломанному компоненту программа должна сообщить, сколько компонентов в итоге потерпит неудачу, и сколько пройдет времени, прежде чем все эти компоненты действительно придут в негодность.

Входные данные

Первая строка содержит количество тестов, не большее 100. Далее для каждого теста:

• первая строка содержит три целых числа n, d и c (1 ≤ n ≤ 10 000, 1 ≤ d ≤ 100 000, 1 ≤ c ≤ n): общее количество компонент в системе, число зависимостей между компонентами и номер компонента, который изначально выходит из строя.

• d строк, содержащие по три целых числа a, b и s (1 ≤ a, b ≤ n и a ≠ b и 0 ≤ s ≤ 1000), указывающие на то что компонент a зависит от компонента b, и способен работать еще s секунд после сбоя b.

В каждом тесте все зависимости (a, b) уникальны.

Выходные данные

Для каждого теста выведите в отдельной строке два целых числа: общее количество компонентов, которые станут неисправными, и количество секунд до того, как все компоненты, которые будут ломаться, придут полностью в негодность.