Friday
Зимни Състезания по Информатика, 2012
Time Limit: 0.5s, Memory Limit: 10MiB
Въпреки безспорните си предимства в много насоки – красива, забавна, и не на последно място интелигентна (или поне тя така твърди), Ели има и един голям недостатък – тя е ужасно суеверна. Момичето изпитва особен страх от числото 13 (както и от Rebecca Black). Макар на пръв поглед това да е нещо малко и незначително, то влияе на голяма част от нейния живот.

Когато се случи денят да е 13-ти петък, нейните суеверия правят живота й (че и на останалите около нея) много неприятен. Например ако пътува нанякъде, Ели брои изминалите минути докато пътува от точка до точка и държи да пристига на всяко място в такива времена, че времето за изминаване на никоя част от нейния маршрут да не се дели на 13. Под "част от маршрут" разбираме един или повече последователни транспорта, които тя е ползвала за да се придвижи в част от пътя. Например ако нейният маршрут е бил дом → спирка1 → спирка2 → край, като времето за пътуване от дома й до първата спирка е T1, времето между двете спирки е T2 и времето от втората спирка до края е T3, то никое от T1, T2, T3, T1 + T2, T2 + T3 и T1 + T2 + T3 не трябва да се дели на 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 реда ще съдържа по три цели числа Ai Bi Ti, означаващи, че от квартал Ai има еднопосочен транспорт до квартал Bi, отнемащ време Ti. Позволено е един и същ квартал да участва повече от веднъж в пътя на Ели.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималното време, за което Ели може да стигне от квартал 1 до квартал N, спазвайки нейните изисквания. Ако това е невъзможно, вместо това изведете -1.
Ограничения
  • 1 ≤ N ≤ 50
  • 1 ≤ М ≤ 2500
  • 1 ≤ Ai, BiN
  • 1 ≤ Ti ≤ 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
В първия пример най-краткият път изисква време 13, правейки го невалиден. Вторият най-кратък път, обаче, е с време 16 и никой негов подинтервал не се дели на 13, следователно е валиден. При второто пътуване единственият възможен път е с време 26, което се дели на 13, следователно няма решение.
Мрън!