رفیق شما در کشوری زندگی می کند که در آستانه ی برگزاری انتخابات مجلس است.
این کشور، n استان و n-1 جاده(مسیر بین 2 استان) دارد و از هر استانی می توان از طریق تعدادی جاده به استانی دیگر رفت. هر استان از 1 تا n شماره گذاری شده و هر جاده از دو حالت خارج نیست: یا "راه سالم" است و یا "راه مشکل دار".
از میان نامزدهای انتخابات، کسی انتخاب می شود که به این وعده عمل کند: "من حداقل k و همچنین k استانی را می یابم که با تعمیر مسیرهای آن k استان منتهی به استان شماره 1 (مثلاً استان شماره 1 پایتخت آن کشور بوده)، هیچ راه مشکل داری در کشور ما وجود نداشته باشد".
حال یکی از فامیل های رفیق تان که در این انتخابات کاندید شده، از شما کمک می خواهد که در عملی شدن این وعده به او کمک کنید.
input
5
1 2 2
2 3 2
3 4 2
4 5 2
output
1 5
