Lovers
ПрАнКА 2009
Time Limit: 0.1s, Memory Limit: 64MiB
Май месец е. Дните са дълги, а нощите - топли и ароматни. Студентските купони се вихрят по цели нощи, момчета и момичета попадат в клопката на любовта под звуците на музиката.

Именно на един такъв купон, под влиянието на голямо количество минерална вода, това се случи и с небезизвестните Ели и Станчо. На следващата сутрин, обаче, двамата осъзнаха, че не всичко е толкова красиво и вълнуващо. Например едно от доста невълнуващите неща е колко път трябва да изминат за да се видят.

Те, разбира се, се опитват да намалят до минимум времето, отделено за пътуване. Това означава, че ако има поредица от автобусни линии, за която пътят от Ели до Станчо бива изминат за минимално време, то те биха избрали нея. Двамата имат карти за всички линии на градския транспорт, затова броят сменени превозни средства не ги интересува. За сметка на това, на всяка спирка автобусите тръгват на всеки Ki минути (броено от нулевата), така че това е възможно да ги забави известно време. Можете ли да помогнете на младата двойка, като намерите път с минимална (по време) дължина между тях?

Схемата на града ще е дадена под формата на граф с N върха (всички спирки) и M насочени ребра (Ai, Bi, Ti) - маршрут на превозно средство от връх Ai до връх Bi за време Ti. За начална спирка ще се счита спирка с номер 1, а за крайна – тази с номер N.
Вход
На първия ред на стандартния вход ще бъдат зададени числата N и M – броят спирки и ребра в графа за текущия тест. На втория ред ще стоят числата К1, К2, ..., КN – през колко минути минава автобус на всяка от N-те спирки. На следващите M реда ще има по една тройка числа Ai Bi Ti – начална спирка, крайна спирка, и време за преминаване между двете. Възможно е да има по повече от едно ребро между Ai и Bi (например автобуси 94 и 280 имат общи спирки). Приемаме, че всички автобуси пристигат едновременно, както и че времето за слизане и качване е пренебрежимо малко - тоест можете да слезете от автобус и веднага да тръгнете с друг. Ако за даден връх i неговото число Ki е, например, 7, то от въпросната спирка може да се тръгне в 0-лева, 7-ма, 14-та, 21-ва и т.н. минута.
Изход
На първия ред на стандартния изход изведете минималното време за стигане от връх 1 до връх N. На следващия ред изведете броя V посетени спирки, с които сте постигнали това време. На третия ред изведете V на брой числа – номерата на върховете по пътя. Ако има няколко такива маршрута, изведете кой да е от тях. Ако пък такъв път не съществува, на единствен ред на стандартния изход изведете -1.
Ограничения
  • 2 ≤ N ≤ 10,000
  • 1 ≤ M ≤ 100,000
  • 1 ≤ Ai, BiN
  • 1 ≤ Ti, Ki ≤ 1,000
Примерен Вход Примерен Изход
5 6 3 19 9 11 5 1 2 17 1 4 3 2 3 8 4 3 18 4 5 33 3 5 15 42 4 1 2 3 5
3 2 6 6 6 1 2 13 3 2 13 -1
В първия тест оптималният път е през върхове 1 -> 2 -> 3 -> 5 с цена 17 (път) + 2 (чакане) + 8 (път) + 0 (чакане) + 15 (път) = 42. Във втория тест се вижда, че ребрата са насочени - няма как да стигнем до връх 3, тъй като никой автобус не ходи до там (само тръгва оттам).
Мрън!