Въпреки безспорните си предимства в много насоки – красива, забавна, и не на последно място интелигентна (или поне тя така твърди), Ели има и един голям недостатък – тя е ужасно суеверна. Момичето изпитва особен страх от числото 13 (както и от Rebecca Black). Макар на пръв поглед това да е нещо малко и незначително, то влияе на голяма част от нейния живот.

Когато се случи денят да е 13-ти петък, нейните суеверия правят живота й (че и на останалите около нея) много неприятен. Например ако пътува нанякъде, Ели брои изминалите минути докато пътува от точка до точка и държи да пристига на всяко място в такива времена, че времето за изминаване на никоя част от нейния маршрут да не се дели на 13. Под "част от маршрут" разбираме един или повече последователни транспорта, които тя е ползвала за да се придвижи в част от пътя. Например ако нейният маршрут е бил дом → спирка1 → спирка2 → край, като времето за пътуване от дома й до първата спирка е T₁, времето между двете спирки е T₂ и времето от втората спирка до края е T₃, то никое от T₁, T₂, T₃, T₁ + T₂, T₂ + T₃ и T₁ + T₂ + T₃ не трябва да се дели на 13.

Нека, например, тези времена са 7, 10 и 16 минути. Тогава T2 + T3 = 26 минути, което се дели на 13 и би провалило деня й. От друга страна, ако времената бяха 7, 14 и 16 минути, то никое от числата 7, 14, 16, 21, 30 и 37 не се дели на 13, следователно нейното пътуване би било успешно.

В града, в който живее Ели, има N квартала, номерирани от 1 до N, включително. Там, също така има M възможни транспорта между кварталите, които Ели е склонна да ползва. За всеки от тях тя знае от кой до кой квартал и за колко време води той. Възможно е някои от транспортите да тръгват и пристигат в един и същ квартал. Помогнете на Ели да намери най-краткия по време път, който води от квартала, където живее Ели (зададен с номер 1) до квартала, където иска да отиде (зададен с номер N). На първия ред на стандартния вход ще бъде зададени две цели числа N и M – съответно броя квартали и броя транспорти. Всеки от следващите M реда ще съдържа по три цели числа A_i B_i T_i, означаващи, че от квартал A_i има еднопосочен транспорт до квартал B_i, отнемащ време T_i. Позволено е един и същ квартал да участва повече от веднъж в пътя на Ели. На единствен ред на стандартния изход изведете едно цяло число – минималното време, за което Ели може да стигне от квартал 1 до квартал N, спазвайки нейните изисквания. Ако това е невъзможно, вместо това изведете -1.

• 1 ≤ N ≤ 50
• 1 ≤ М ≤ 2500
• 1 ≤ A_i, B_i ≤ N
• 1 ≤ T_i ≤ 100

Примерен Вход	Примерен Изход
5 5 1 2 1 1 3 2 2 4 1 3 4 3 4 5 11	16
2 1 1 2 26	-1