*(Л. Шастин) Группа авантюристов хочет добраться до максимально возможно отдаленной от экватора зоны Земли, для чего им предстоит пересечь множество других зон в качестве перевалочных пунктов. При посещении очередной зоны авантюристы затрачивают некоторую сумму денежных единиц на организацию перевала, эта сумма может варьироваться в зависимости от отправной и конечной зоны. Группа начинает свой путь в зоне № 1, а изначальные затраты средств равны нулю. Известно, что чем больше номер зоны, тем дальше она расположена от экватора. Имеется N записей, каждая из которых содержит информацию о какой-то зоне: номер текущей зоны, номер переходной зоны, до которой можно добраться отсюда и сумма средств для посещения переходной зоны. Каждая зона может быть представлена в нескольких вариантах с разными переходными пунктами и ценами за переход. Из каждой зоны можно попасть только в зону с бóльшим номером. Некоторые записи также могут содержать информацию о недостижимых зонах (в которые невозможно попасть, начав движение из зоны № 1). Определите номер максимальной зоны, которой могут достигнуть авантюристы, если их бюджет составляет K денежных единиц, а также максимальный возможный остаток средств при этих условиях.
Входные данные. В первой строке входного файла 26-168.txt записаны два натуральных числа: N (N ≤ 100 000) -- количество записей о зонах и K (K ≤ 1 000 000) -- бюджет, которым располагает группа. В каждой из следующих N строк находятся по три числа: номер текущей зоны, номер переходной зоны (в которую можно передвинуться из текущей) и сумма средств, необходимая для перехода. Все числа натуральные и не превосходят 1 000 000.
Запишите в ответе два числа: максимальный номер зоны, которой могут достигнуть авантюристы, если их бюджет составляет K денежных единиц, а также максимальный возможный остаток средств при этих условиях.
Пример входного файла:
8 100
1 4 20
2 4 30
1 3 10
3 4 5
4 5 5
1 2 10
3 5 20
2 5 50
При таких исходных данных можно достигнуть максимум зоны №5 несколькими способами. Оптимальным вариантом движения будет переход из зоны 1 в зону 3 за 10 единиц, затем из зоны 3 в зону 4 за 5 единиц и в конце из зоны 4 в зону 5 за 5 единиц. Остаток бюджета при этом составит 100 -- 20 = 80 единиц. Ответ: 5 80.