პოლიცია

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 512 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


ერთ უცნობ ქვეყანაში n (2 <= n <= 1000) ქალაქია, რომლებიც გადანომრილია 1-დან n-ის ჩათვლით ნატურალური რიცხვებით. ზოგიერთ ორ ქალაქს შორის არის ორმხრივი პირდაპირი გზა (1 <= "პირდაპირი გზის სიგრძე" <= 1000) ისე, რომ ნებისმიერი ქალაქიდან შეიძლება მოხვდე ნებისმიერ სხვა ქალაქში ერთადერთი მარშრუტით.

ბოლო დროს ქვეყანაში გახშირებული ქურდობების გამო, მთავრობამ გადაწყვიტა ორ განსხვავებულ ქალაქში ააშენოს პოლიციის სადგური ისე, რომ უდიდესი მანძილი პოლიციის სადგურებიდან ქალაქებამდე იყოს მინიმალური. პოლიციის სადგურებიდან ქალაქამდე მანძილი არის ამ ქალაქიდან ორივე სადგურამდე მანძილებს შორის მინიმალური.

თქვენი ამოცანაა დაეხმაროთ ქვეყნის მთავრობას ორი ქალაქის ამორჩევაში პოლიციის სადგურებისათვის და სადგურებიდან უშორეს ქალაქამდე მანძილის პოვნაში.


შესატანი მონაცემები:

პირველ სტრიქონში წერია n, ხოლო მომდევნო (n – 1) სტრიქონიდან თითოეულში წერია სამი ერთმანეთისაგან ჰარით გამოყოფილი მთელი u, v და d რიცხვი, სადაც u და v არის ერთმანეთთან პირდაპირი გზის მქონე ორი განსხვავებული ქალაქის ნომრები ხოლო d მათ შორის მანძილი.


გამოსატანი მონაცემები:

ერთადერთ სტრიქონში უნდა დაბეჭდოთ სამი ერთმანეთისაგან თითო ჰარით გამოყოფილი მთელი u, v და d რიცხვი, სადაც u და v (u < v) არის იმ ქალაქების ნომრები, სადაც უნდა აშენდეს პოლიციის სადგურები, თუ ასეთი რამდენიმე წყვილია მაშინ მათ შორის უნდა ამოვირჩიოთ ისეთი რომელშიც u არის მინიმალური და თუ ისევ ასეთი წყვილი რამდენიმეა მაშინ ისეთი რომელშიც უკვე v არის მინიმალური. d კი არის სადგურებიდან ყველაზე შორს მყოფ ქალაქამდე მანძილი.




მაგალითები

შესატანი მონაცემები
5 1 5 1 5 2 10 2 3 2 2 4 3 დაკოპირება
გამოსატანი მონაცემები
1 2 3 დაკოპირება

შენიშვნა

კომენტარი განხილულ მაგალითზე:

სულ ქვეყანაში არის 5 ქალაქი, პირველ და მეხუთე ქალაქებს შორის არსებული გზის სიგრძეა 1, მეხუთე და მეორე ქალაქებს შორის არსებული გზის კი 10 და ა.შ.. პოლიციის სადგურები კი უნდა აშენდეს პირველ და მეორე ქალაქებში ხოლო მათგან ყველაზე შორს მყოფია მეოთხე ქალაქი, რომლიდანაც უახლოეს სადგურამდე (მეორე ქალაქამდე) მანძილია 3. ასევე სადგურები შეიძლებოდა აშენებულიყო მეორე-მეხუთე ქალაქებში.