— Как я мог забыть?! Через T часов нам нужно показать альфа-версию нашей игры потенциальному инвестору. От этой встречи будет зависеть, сможем ли мы завершить разработку игры.
— Без паники! Где мы с ним встречаемся?
— В его офисе, в Тмутаракани. Выезжаем прямо сейчас. Думаю, мы успеем, только в паре мест нужно будет превысить максимальную разрешённую скорость.
— Лишние проблемы с дорожной полицией нам ни к чему — они тоже отнимут время. Сейчас мы придумаем такой маршрут, чтобы успеть вовремя и чтобы максимальное превышение скорости на нём было минимально возможным.

В первой строке даны целые числа n и m — количество перекрёстков и дорог между ними (2 ≤ n ≤ 10 000; 1 ≤ m ≤ 10 000). Все дороги двусторонние. В i-й из следующих m строк записаны целые числа a_i, b_i, s_i и l_i, означающие, что между перекрёстками a_i и b_i есть дорога длиной l_i километров с максимальной разрешённой скоростью движения s_i километров в час (1 ≤ a_i < b_i ≤ n; 1 ≤ s_i ≤ 300; 1 ≤ l_i ≤ 1000). Офис разработчиков игры находится на перекрёстке 1, офис инвестора — на перекрёстке n. Гарантируется, что от перекрёстка 1 до перекрёстка n можно доехать по дорогам. В последней строке записано целое число T — время в часах, оставшееся до встречи (1 ≤ T ≤ 10⁶).

В первой строке выведите два числа S и k — на сколько километров в час минимум придётся превысить скорость, чтобы успеть на встречу, и количество дорог, по которым нужно будет проехать. Во второй строке через пробел выведите k чисел — номера этих дорог в том порядке, в котором по ним нужно ехать. Дороги пронумерованы целыми числами от 1 до m в соответствии с тем, как они перечислены во входных данных. Если существует несколько способов добраться до офиса инвестора, превысив скорость на S километров в час, можно вывести любой из них. Абсолютная или относительная погрешность S не должна превосходить 10⁻⁶.