В стране имеется ровно n городов, пронумерованные натуральными числами от 1 до n. В каждом городе находится аэропорт.

Также в стране имеется единственная авиакомпания, которая совершает m рейсов. К сожалению, чтобы воспользоваться ими, вам требуется быть постоянным клиентом этой компании, а именно, вы имеете возможность пользоваться рейсом номер i из города a_i в город b_i только в том случае, если вы уже совершили не менее d_i перелетов с использованием рейсов авиакомпании.

Обратите внимание, что рейс с номером i летит именно из города a_i в город b_i. Им нельзя воспользоваться, чтобы прилететь из города b_i в город a_i. Интересная особенность услуг, предоставляемых авиакомпанией, заключается в том, что бывают развлекательные полеты с прекрасным видом на небо, которые начинаются и заканчиваются в одном и том же городе.

Вам необходимо попасть из города 1 в город n. К сожалению, до этого вы никогда не путешествовали самолетом. Какое минимальное число перелетов вам потребуется, чтобы осуществить это путешествие?

Обратите внимание, что одним и тем же рейсом можно летать несколько раз.