შინ დაბრუნება

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

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

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

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

წყარო: USACO, 2004/05, NOV, QUAL


ბესი მინდორშია და უნდა რომ რაც შეიძლება სწრაფად დაბრუნდეს ბოსელში, რათა კარგად გამოძინება მოასწროს, თორემ დილას ჯონი გააღვიძებს მოსაწველად.

ფერმერ ჯონის ნაკვეთი ჭაობითაა დაფარული და ამ ჭაობებში მიმოფანტულია N (2 <= N <= 1000) ცალი კუნძული, რომლებიც გადანომრილია 1..N. კუნძული 1 არის ბოსელი; იმ კუნძულის ნომერი კი, რომელზეც ვაშლის ხე დგას და რომლის ძირშიც ბესი ბალახობს, არის N. კუნძულიდან კუნძულზე მხოლოდ ბილიკებით შეიძლება გადასვლა. სულ არის T (1 <= T <= 2000) ცალი სხვადასხვა სიგრძის ორმხრივი ბილიკი.

 მოცემულია ბილიკების განლაგება და სიგრძეები. უნდა განსაზღვროთ რა მინიმალური სიგრძის გზა უნდა გაიაროს ბესიმ ბოსლამდე მისასვლელად. გარანტირებულია, რომ ერთი მაინც ასეთი გზა აუცილებლად არსებობს.

შეტანის ფორმატი:

* სტრიქონი 1: ჰარით გამოყოფილი ორი მთელი რიცხვი: T და N

 

* სტრიქონები 2..T+1: თითოეული სტრიქონი განსაზღვრავს ბილიკს ჰარით გამოყოფილი სამი რიცხვის საშუალებით. პირველი ორი არის კუნძულების ნომერი, რომლებსაც ეს ბილიკი აერთებს, ხოლო მესამე რიცხვი არის ბილიკის სიგრძე დიაპაზონში 1..100.

 

გამოტანის ფორმატი:

 * სტრიქონი 1: ერთი მთელი რიცხვი, რომელიც არის მინიმალური მანძილის სიგრძე, რაც უნდა გაიაროს ბესიმ N კუნძულიდან კუნძულ 1-მდე მისაღწევად.

 

 

 

 




მაგალითები

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

შენიშვნა

სულ არის ხუთი კუნძული და ხუთი სხვადასხვა ბილიკი. ბესიმ თანმიმდევრობით უნდა გაიაროს 4, 3, 2, და 1 ბილიკები.