Tanışlıq#5273
N-Regionundan istedadlı bir qrup məktəbli qız respublika olimpiadasına gəlib. Delegasiya qızdan ibarətdir və gözlənilməz bir vəziyyətə görə, hər bir qız ayrı-ayrı tək nəfərlik otel otağında yerləşdirilib.
Olimpiada turundan əvvəl bir axşam, qəfil elektrik kəsintisi otaqlardan birinə təsir etdi. Həmin otaqda qalan qız hazırlığına davam etmək üçün ən yaxın rəfiqəsinin otağına getmək qərarına gəldi. Onun ən yaxın rəfiqəsinə çatması üçün lazım olan vaxt onların otaqları arasındakı məsafədən asılıdır.
Təşkilatçılar müəyyən etmək istəyirlər ki, hansı iştirakçıya elektrik kəsintisi təsir etdikdə, ən yaxın rəfiqəsinə çatmaq üçün maksimum məsafəni getməli olacaq və bu maksimal məsafə nə qədərdir.
Birinci sətirdə və (1 \leq n,\, k \leq 10^{5}) — nümayəndə heyətindəki qızların sayı və onların arasındakı dostluq cütlərinin sayı verilir.
Növbəti sətrin hər birində üç ədəd var: a_i, b_i və w_i — iki rəfiqənin nömrəsi və onların otaqları arasındakı məsafə (1 \leq a_i,\, b_i \leq n, a_i \neq b_i, 1 \leq w_i \leq 10^{5}).
Zəmanət verilir ki, heç bir dostluq cütü iki dəfə qeyd olunmayıb və hər bir qızın ən azı bir rəfiqəsi var.
Birinci sətirdə, hər hansı qıza elektrik kəsintisi təsir etdikdə, onun ən yaxın rəfiqəsinə çatmaq üçün getməli olduğu maksimal məsafəni çap edin.
İkinci sətirdə isə, bu maksimal məsafəni gedəcək qızın nömrəsini çap edin. Əgər belə qız bir neçədirsə, onlardan istənilən birinin nömrəsini çap edin.
Nümunə 1