კავშირები

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

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

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

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

წყარო: პოლონეთი, ოლიმპიადა 10, ეტაპი 2


ბაიტოთიის ინფრასტრუქტურის სამინისტრომ გადაწყვიტა შექმნას კომპიუტერული პროგრამა, რომელიც დაეხმარებთ ქალაქებს შორის არსებული გზების სიგრძეების სწრაფად დათვლაში. გასაკვირი არ არის, რომ ბაიტოთიის მოსახლეობას ყოველთვის უნდოდა უმოკლესი მარშრუტების პოვნა, მაგრამ როგორც აღმოჩნდა მათ ასევე აინტერესებთ რომელია k-ური უმოკლესი მარშრუტი. მარშრუტებში ციკლები დაშვებულია, ანუ შეიძლება მასში ერთიდაიმავე ქალაქი რამდენჯერმე შედიოდეს. მაგალითად: თუ 2 ქალაქს შორის არსებობს 4 სხვადასხვა მარშრუტი და მათი სიგრძეებია 2, 4, 4 და 5, მაშინ უმოკლესი კავშირის სიგრძე იქნება 2, მეორე უმოკლესის - 4, მესამისაც 4 და მეოთხის 5.

დაწერეთ პროგრამა, რომელიც:

      წაიკითხავს სტანდარტული შესატანი მონაცემებიდან ბაიტოთიის გზების ქსელს და მონაცემებს მარშრუტების სიგრძეების შესახებ

      დათვლის და დაბეჭდავს სტანდარტულ output-ში წაკითხული ინფორმაციის შესაბამის პასუხებს

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

პირველ ხაზზე შემოდის ორი ინტეჯერი: n და m, რომლებიც ერთმანეთისგან ერთი space-ით არიან დაშორებულები. 1 n 100, 0 m n2 – n. n – ქალაქების რაოდენობა ბაიტოთიაში, m – გზების რაოდენობა ქალაქებს შორის. ქალაქები გადანომრილია 1-დან n-მდე.

 მომდევნო m ცალ ხაზზე მოცემულია space-ებით დაშორებული 3-3 ინტეჯერი a, b და l. a ≠ b, 1 ≤ l ≤ 500. თითოეული სამეული აღწერს ცალმხრივ l სიგრძის გზას a-დან b-მდე. ყოველ 2 ქალაქს შორის არსებობს მაქსიმუმ ერთი ცალმხრივი გზა, რომლითაც ამ მიმართულებით შეიძლება მოძრაობა.

 მომდევნო ხაზზე მოცემულია 1 ინტეჯერი q, 1 ≤ q ≤ 10 000, რომელიც შემომავალი მონაცემების რაოდენობას განსაზღვრავს. მომდევნო q ხაზიდან თითოეულზე წერია 3 ცალი ინტეჯერი, რომლებიც ერთმანეთისგან space-ებით არიან დაშორებულნი: c, d და k, 1 ≤ k ≤ 100. ეს მონაცემები განსაზღვრავს k-ურ უმოკლეს გზას c ქალაქიდან d ქალაქისკენ.

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

თქვენმა პროგრამამ უნდა გამოიტანოს პასუხები წაკითხული მონაცემების შესაბამისად, ყოველი პასუხი ახალ ხაზზე. i-ურ ხაზზე უნდა დაბეჭდოთ i-ური მონაცემის შესაბამისი პასუხი: ერთი ინტეჯერი, რომელიც იქნება საძიებელი მარშრუტის სიგრძე ან -1, თუ ასეთი მარშრუტი არ არსებობს.




მაგალითები

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

შენიშვნა

 

თარგმანი შესრულებულია ანამარია ჩხაიძის მიერ