მაფია

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

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

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

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

წყარო: GEOI, 2010, დასკვნითი, XI-XII კლასი


ერთ შორეულ ქვეყანაში არის ორი დაპირისპირებული მაფიოზური კლანი. მათ შორის ომის დაწყების თავიდან ასაცილებლად გადაწყდა შეხვედრის მოწყობა. ამისათვის უნდა შეირჩეს ქალაქი, სადაც მივა ორივე კლანის თითო წარმომადგენელი. 
    სულ ქვეყანაში N ქალაქია, რომლებიც ერთმანეთთან დაკავშირებული არიან M რაოდენობის ორმხრივი გზით, რომელთა გასავლელად საჭირო დროები ცნობილია. ყოველ ქალაქში შეიძლება ცხოვრობდეს რომელიმე კლანის წარმომადგენელი (მაგრამ არა ორივესი). დანიშნულ ქალაქში შეხვედრა მოხდება მაშინ, როდესაც იქ იქნება ორივე კლანის წარმომადგენელი. იპოვეთ, რა მინიმალურ დროში შეიძლება მოხდეს ეს შეხვედრა თუ ქალაქის, კლანების წარმომადგენლების და მათ მიერ დანიშნულების ადგილამდე გასავლელი გზების შერჩევა მოხდება საუკეთესო შესაძლო ხერხით.
 
    შესატანი მონაცემები:
    პირველ სტრიქონში მოცემულია ერთი ჰარით გამოყოფილი ორი ნატურალური რიცხვი: N(2≤N≤100,000) და M(1≤M≤200,000) – ქალაქების და გზების რაოდენობები, შესაბამისად. ქალაქები გადანომრილია მთელი რიცხვებით 1 დან N-მდე. შემდეგი M რაოდენობის სტრიქონიდან თითოეული აღწერს ერთ გზას ჰარებით გამოყოფილი სამი a, b და c მთელი რიცხვით (1 ≤ a, b ≤ N, a ≠ b, 1 ≤ c ≤ 10,000), რაც იმას აღნიშნავს, რომ ქალაქები ნომრებით a და b არიან დაკავშირებული გზით, რომლის გავლისთვის საჭირო დროა c, გავლის მიმართულების მიუხედავად. არცერთ ორ ქალაქს შორის არ იქნება ერთზე მეტი პირდაპირი გზა.
    ბოლო სტრიქონში არის N სიმბოლო, ჰარების გარეშე. თუ i-ურ ქალაქში არის პირველი კლანის წარმომადგენელი, ამ სტრიქონში i-ური ციფრი იქნება 1. თუ იქ არის მეორე კლანის წარმომადგენელი, ეს რიცხვი იქნება 2. ხოლო, თუ ამ ქალაქში არ არის არცერთი კლანის წარმომადგენელი, შესაბამისი რიცხვი იქნება 0. 
    გამოსატანი მონაცემები:
    ერთადერთ სტრიქონში გამოიტანეთ შეხვედრის მინიმალური დრო. თუ შეხვედრა შეუძლებელია, გამოიტანეთ სიტყვა ”WAR”.



მაგალითები

შესატანი მონაცემები
7 6 1 3 10 3 5 4 4 5 3 6 7 1 2 3 5 3 4 8 1102022 დაკოპირება
გამოსატანი მონაცემები
7 დაკოპირება
შესატანი მონაცემები
8 4 1 2 1 4 3 2 8 7 3 6 5 4 11220201 დაკოპირება
გამოსატანი მონაცემები
WAR დაკოპირება
შესატანი მონაცემები
4 3 1 2 1000 2 3 999 3 4 1000 2121 დაკოპირება
გამოსატანი მონაცემები
999 დაკოპირება

შენიშვნა

 პირველ მაგალითში შეხვედრის ადგილად უნდა შეირჩეს მე-3 ქალაქი, სადაც პირველი კლანის წარმომადგენელი პირდაპირ მივა მე-2 ქალაქიდან დროის 5 ერთეულში, ხოლო მეორე კლანის წარმომადგენელი მივა მე-4 ქალაქიდან მე-5 ქალაქის გავლით, ანუ 3+4=7 დროის ერთეულში და შეხვედრაც დაიწყება.
მეორე მაგალითში შეხვედრა შეუძლებელია, ხოლო მესამეში უნდა შეხვდნენ მე-2 და მე-3 ქალაქის წარმომადგენლები რომელიმე მათგანის ამჟამინდელ საცხოვრებელ ქალაქში.