Thirteen
TopCoder MRM 471
Time Limit: 0.2s, Memory Limit: 64MiB
Въпреки безспорните си предимства в много насоки – красива, забавна, и не на последно място интелигентна (или поне тя така твърди), Ели има и един голям недостатък – тя е ужасно суеверна.

Това на пръв поглед дребно нещо, влияе на голяма част от нейното ежедневие. Примерно уговорките за дискотека с нейните приятелки са крайно сложна задача. Тръгвайки нанякъде, Ели брои изминалите минути и не иска да си позволи да пристигне където и да е, във време, делящо се на 13 (заклеймено за едно от най-фаталните числа). Например ако пътят й до магазина отнема 13 минути, това прави напълно недопустимо за нея да отиде и да напазарува. Нещо повече, ако иска да отиде от точка А до точка B и трябва да смени няколко превозни средства, тя не бива да пристига в нито една от спирките във време, делящо се на 13 (13, 26, 39, ...). Да кажем, ако пътуванията й с автобусите са с продължителност 7, 10 и 9 минути, то при слизане от третия тя ще пристигне във време 26, което се дели на 13 и би повлияло зле на нейния ден. От друга страна ако пътуванията са с продължителност 7, 13 и 9 минути, тя ще пристига на спирките във времена 7, 20 и 29, никое от които не е фатално и съответно това е допустим маршрут.

В града, в който живее Ели, има N квартала, номерирани от 1 до N, включително. Там, също така има M възможни транспорта между кварталите, които Ели е склонна да ползва. За всеки от тях тя знае от кой до кой квартал и за колко време води той. Възможно е някои от транспортите да тръгват и пристигат в един и същ квартал, а както и да има по повече от един възможен транспорт между двойка квартали.

Помогнете на Ели да намери най-краткия по време път, който води от квартала, където живее Ели (зададен с номер 1) до квартала, където иска да отиде (зададен с номер N). Един и същ квартал може да участва повече от веднъж в пътя на Ели.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M – съответно броя квартали и броя транспорти. Всеки от следващите M реда ще съдържа по три цели числа Ai Bi Ti, означаващи, че от квартал Ai има еднопосочен транспорт до квартал Bi, отнемащ време Ti.
Изход
На единствен ред на стандартния изход изведете по едно цяло число – минималното време, за което Ели може да стигне от квартал 1 до квартал N, спазвайки нейните изисквания. Ако това е невъзможно, вместо това изведете -1.
Ограничения
  • 2 ≤ N ≤ 10,000
  • 1 ≤ М ≤ 100,000
  • 1 ≤ Ai, BiN
  • 1 ≤ Ti ≤ 1,000
Примерен Вход Примерен Изход
5 6 1 2 19 1 3 22 2 3 7 2 4 33 3 4 41 4 5 17 80
2 1 1 2 26 -1
Тук най-късият път е с дължина 69, което го прави невалиден. Вторият най-къс, макар и с по-голяма дължина (80), е окей. Забележете, че ребрата са насочени, иначе най-късият път би бил с дължина 79 (1-3-2-4-5).
Във втория пример единственият възможен транспорт пристига във време, делящо се на 13.
Мрън!