Olimpiya Hava Yolları#4975
İmperator Olimpiya, imperiyanın N şəhərini hava nəqliyyatı ilə birləşdirmək qərarına gəlib. Saray proqramçısına, uçuş xəritəsinin qurulmasını asanlaşdırmaq üçün OlimpTikinti adlı bir proqram yazmaq tapşırılıb. Bu proqram, üç parametrdən A, B və C asılı olan iki növ əməliyyatı yerinə yetirməlidir:
A şəhərindən B şəhərinə yeni bir uçuş əlavə edin, bu uçuş C dəqiqə davam edir.
A şəhərində başlayan bütün uçuşları nəzərdən keçirin. Bu uçuşlardan i-ci uçuş v_i şəhərində bitir və t_i dəqiqə davam edir. Hər bir belə i üçün B şəhərindən v_i şəhərinə t_i + C dəqiqə davam edən bir uçuş yaradın.
Bütün əməliyyatlar tamamlandıqdan sonra proqram, hər bir şəhər üçün, bəlkə də digər şəhərlərdə transferlərlə, paytaxtdan ora uçmaq üçün lazım olan ən qısa vaxtı tapmalıdır. Qeyd edək ki, hava limanında enmə, qalxma və gözləmə vaxtı sıfırdır.
İki şəhər arasında bir neçə uçuş ola bilər və bu uçuşlar müxtəlif vaxt ala bilər. Eyni şəhərdə başlayıb bitən uçuşlar da mövcud ola bilər. Bütün uçuşlar birtərəflidir, yəni A şəhərindən B şəhərinə birbaşa uçuşun olması, B şəhərindən A şəhərinə birbaşa uçuşun mövcudluğunu təmin etmir.
OlimpTikinti proqramı tərəfindən yerinə yetirilən M əməliyyat ardıcıllığı üçün proqram yazın ki, hər bir şəhər üçün, paytaxtdan başqa, bu şəhərə uçmaq üçün lazım olan ən qısa vaxtı tapsın.
Birinci sətir, Olimpiya imperiyasında şəhərlərin sayı və OlimpTikinti proqramı tərəfindən yerinə yetirilən əməliyyatların sayı olan iki tam ədəd N və M (2 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5) ehtiva edir. Növbəti M sətirdə növbəti əməliyyat haqqında məlumat var. Sətirdəki ilk rəqəm, əgər yerinə yetirilən əməliyyat birinci növdədirsə 1, ikinci növdədirsə 2 bərabərdir. Sonra üç tam ədəd A, B və C (1 ≤ A ≤ N, 1 ≤ B ≤ N, -10^8 ≤ C ≤ 10^8) yazılmışdır, onların mənası yuxarıda təsvir edilmişdir. Şəhərlər 1-dən N-ə qədər nömrələnir; paytaxt 1 nömrəlidir. Uçuş vaxtının hər bir uçuş üçün mütləq müsbət olacağı təmin edilir.
N - 1 sətir çıxarın. Onlardan i-ci sətirdə paytaxtdan i + 1 nömrəli şəhərə uçmaq üçün mümkün olan ən qısa vaxt dəqiqələrlə göstərilməlidir. Hər hansı bir şəhərə çatmaq mümkün deyilsə, müvafiq sətirdə -1 rəqəmini çıxarın.
Nümunə 1