DJ Krisa T
Турнир за Купата на Декана, 2011
Time Limit: 1s, Memory Limit: 64MiB
Ели е момиче, и като такова винаги закъснява. В момента тя закъснява за концерта на небезизвестната ди-джей-ка DJ Krisa T., също позната като нейната приятелка Крис. До началото на концерта остават броени минути (всъщност точно K минути), а Ели тъкмо излиза от тях. Разбира се, тя може да си вземе такси и да стигне на време, но кой дава пари за глупости. Вместо това тя мисли да си вземе карта за градския транспорт и да спести някой лев (който да бъде инвестиран в нещо по-пенливо).

Градският транспорт в града, където живеят, е малко по-странно устроен. В него различните линии могат да имат различна цена – ако са по-бързи или по-нови те могат да са по-скъпи от други. Ако Ели си купи карта за градската мрежа на стойност X, тя може да пътува с всички линии, чиято цена е по-малка или равна на X колкото си пъти иска, но не може да пътува с по-скъпи.

По дадена информация къде се намира тя, къде трябва да стигне, както и всички линии на градския транспорт (от къде до къде водят, колко струват, и колко минути отнема за да се стигне от едната точка до другата) намерете цената на най-евтината карта, с която Ели може да стигне на време (тоест за не повече от K минути). Забележете, че Ели ще си купи само картата, без да ползва допълнителни билетчета за по-скъпи линии.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, M и K – съответно броят спирки, броят маршрути и оставащото време до концерта. На всеки от следващите M реда ще бъде зададен един маршрут чрез четворката цели числа Ai Bi Pi Ti, указваща, че има линия (насочено ребро) от спирка Ai до спирка Bi с цена Pi и продължителност Ti. Считаме, че Ели живее до спирка 1, а концертът се намира до спирка N.
Изход
На стандартния изход изведете едно единствено цяло число – минималната цена на карта за градски транспорт, с която Ели може да стигне навреме. Ако тя не може да стигне, дори ако вземе карта, с която да ползва всички линии, вместо това изведете -1.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ M ≤ 300,000
  • 1 ≤ AiBiN
  • 1 ≤ Pi, Ti, K ≤ 1,000,000
Примерен Вход Примерен Изход
7 11 42 1 3 7 11 3 1 7 13 1 2 3 3 1 4 13 1 6 1 14 8 4 6 1 7 2 4 1 13 2 6 4 20 3 5 2 5 5 6 6 4 6 7 5 20 7
2 2 3 1 2 3 5 1 2 1 9 -1
В първия пример има пътища с цена 5, но тяхното време за преминаване е съответно 43 и 45, при ограничение 42. Също така има път с време 28, но пък неговата цена е 13. Оптималният път е 1-3-5-6-7, чиято цена е 7 и време за преминаване 40.
Мрън!