İdeal Yol
Yeni Lostland əyləncə parkında yeni bir labirint attraksionu açılıb. Labirint n otaqdan və m keçiddən ibarətdir. Hər bir keçid müəyyən bir rəngə c_i boyanıb. Labirintin ziyarətçiləri helikopterdən birinci otağa atılır və onların məqsədi labirintin çıxışına, yəni n nömrəli otağa çatmaqdır.
Labirint sahibləri sabah bir yarış keçirməyi planlaşdırırlar. Bir neçə qaçışçı birinci otağa atılacaq. Onlar n nömrəli otağa qaçaraq keçidlərin rənglərini qeyd edəcəklər. Ən qısa rəng ardıcıllığına malik olan iştirakçı yarışın qalibi olacaq. Əgər bir neçə iştirakçının ardıcıllıq uzunluğu eynidirsə, ideal yola malik olan qalib olacaq. Yol ideal yol hesab olunur, əgər onun rəng ardıcıllığı ən qısa yollar arasında leksikoqrafik olaraq ən kiçikdirsə.
Andrew yarışa hazırlaşır. O, Yeni Lostland üzərində helikopter turu etdi və labirintin şəklini çəkdi. Sizin vəzifəniz ona birinci otaqdan n nömrəli otağa ideal yolu tapmaqda kömək etməkdir ki, o, yarışda qalib gələ bilsin.
Giriş verilənləri
Giriş faylının birinci sətri otaqların və keçidlərin sayı olan n və m tam ədədlərini ehtiva edir (2 ≤n ≤ 100000, 1 ≤ m ≤ 200000). Növbəti m sətir keçidləri təsvir edir, hər bir keçid üç tam ədəd ilə təsvir olunur: a_i, b_i və c_i — keçidin birləşdirdiyi otaqların nömrələri və onun rəngi (1 ≤ a_i, b_i ≤ n, 1 ≤ c_i ≤ 10^9). Hər bir keçid hər iki istiqamətdə keçilə bilər. İki otaq bir neçə keçid ilə birləşdirilə bilər, bir otaqdan özünə keçid ola bilər. Birinci otaqdan n nömrəli otağa çatmağın mümkün olduğu təmin edilir.
Çıxış verilənləri
Çıxış faylının birinci sətri k — birinci otaqdan n nömrəli otağa ən qısa yolun uzunluğunu ehtiva etməlidir. İkinci sətir k ədəd — ideal yolda keçilməli olan keçidlərin rənglərini ehtiva etməlidir.