Задача . 66169

Одна очень известная компания Я&Ко захотела создать сеть доставок из ресторанов и кафе по всему городу, притом доставку производили бы мини-поезда. Главной проблемой стала логистика – как добраться из точки отправления в точку назначения самым быстрым способом. Но так как мини-поезда представляли собой только прототип, то в них был очень плохо проработан аккумулятор, что заставило компанию подумать про эту проблему тщательнее.
Я&Ко решили проложить рельсы между всеми точками доставки и по некоторым рельсам пустить зарядку, чтобы мини-поезда могли ехать и заряжаться. Компания решила устроить среди всех программистов, кто сможет решить их задачу, соревнование. Далее выбрать победителя, но как, пока неизвестно.
Задача состоит в следующем – есть известная карта маршрутов в городе, которая представлена в виде направленного взвешенного графа с возможными циклами. На каждом ребре графа даны значения времени перемещения между связанными вершинами и заряжает рельс или нет на этом маршруте.
За 1 минуту по рельсам зарядки мини-поезд заряжается на 10%. Если он зарядился, но всё ещё в пути на зарядных рельсах, то его заряд составляет 100%.
Для простоты расчёта количество минут мини-поезда после съезда с рельсов округляется вверх к ближайшему целому (например, поезд максимально может проехать 30 минут, что означает его 100% заряда, на рельс он заехал, когда у него осталось заряда на 10 минут, пусть время в пути по рельсу составило 4 минуты, значит зарядился он на 40%, что составляет 12 минут, потому после съезда с зарядного рельса у него останется запас хода на 10 + 12 = 22 минуты.
Задача – найти минимальное время, за которое мини-поезд сможет доехать до клиента со стартовой точки, если точно известно, что он это сделать сможет.

Входные данные
на первой строке подаются два целых числа (1 <= N,M <= 1000), где N – количество вершин графа, M - количество рёбер.
на второй строке подаётся целое число T (1 <= T <= 100), где T – время, которое может проехать полностью заряженный мини-поезд;
на третьей строке подаются через пробел два целых числа – номер стартовой вершины и номер конечной вершины;
далее на M строках подаются рёбра графа через пробел с указанием зарядный рельс на данном пути или нет (0 – не зарядный, 1 – зарядный) (<откуда> <куда> <время в пути> <признак зарядного рельса>).
Выходные данные
выведите на первой строке количество минут, которое понадобится мини-поезду, чтобы полностью доехать до клиента (конечной точки) в виде одного целого числа.

Примечание
•робот изначально заряжен на 100%.