Погані дороги#4956
У країні є декілька міст, з'єднаних дорогами. Через недостатній бюджет деякі дороги мають вибоїни, тому певні машини не можуть ними користуватися. У кожної дороги задана висота — мінімальна висота днища машини, яка може проїхати цією дорогою. Деякі дороги приватні, і за проїзд по них потрібно платити. Плата за кожну таку дорогу стандартизована й дорівнює одній стандартній одиниці. Для кожної такої дороги також відомий потрібний час для проїзду.
Вам потрібно доїхати з міста до міста , витративши не більше хвилин та не більше стандартних одиниць. Знайдіть мінімальну висоту днища машини, що дозволяє здійснити цю поїздку.
У першому рядку задано кількість міст (1 \leq n \leq 100), кількість доріг (1 \leq m \leq 10^4), початкове місто та кінцеве місто (1 \leq s, t \leq n). У другому рядку — (0 \leq \text{money} \leq 10^6) та (0 \leq \text{maxtime} \leq 10^6).
Далі у кожному з наступних рядків описується дорога у форматі: u_i v_i c_i t_i h_i. Тут u_i — початкове місто -ої дороги, v_i — кінцеве місто, c_i дорівнює , якщо дорога приватна (інакше ), t_i — час проїзду по цій дорозі, а h_i — необхідна висота днища машини (1 \leq u_i, v_i \leq n, 0 \leq t_i \leq 10^4, 0 \leq h_i \leq 10^6). Всі дороги — односторонні. Всі числа вхідних даних — цілі.
Якщо шлях із у із заданими обмеженнями відсутній, виведіть -1. Інакше у першому рядку виведіть мінімальну необхідну висоту днища машини; у другому рядку — кількість доріг на обраному маршруті; у третьому рядку — індекси (від до , у порядку вхідних даних) доріг, які використовуються для проїзду з у , у тому порядку, у якому вони проходяться.
Приклад 1