Одного разу король Флатландії вирішив відправити k своїх синів на пшуки наречених. Усім відомно, що у Флатландії n міст, деякі з яких з'єднано дорогами. Король живе у столиці, яка має номер 1, а місто під номером n знамените своїми нареченими.

Отже, король звелів, щоб кожен з його синів діставлся по дорогам з міста 1 у місто n. Оскільки, недивлячись на достатню кількість наречених у місті n, красивих снред них не так вже й багато, сини стережуться один одного. Тому вони хочуть дістатись до мети таким чином, щоб ніякі два сини не проходили по одній і тій же дорозі (навіть у різний час). Так як король любить своїх синів, він хоче, щоб середній час сина у дорозі до міста призначення був мінімальним.

Вхідні дані

У першому рядку знаходяться числа n, m та k (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ k ≤ 100) - кількість міст та доріг у Флатландії і синів короля, відповідно. Наступні m рядків містять по три цілих додатних числа кожен - міста, які з'єднує відповідна дорога та час, який потрібно для її проходження (час не перевищує 106). По дорозі можна переміщуватись у довільному з двох напрямків, два міста можуть бути з'єднані декількома дорогами.

Вихідні дані

Якщо виконати наказ короля неможливо, виведіть у першому рядку число -1. У протилежному випадку виведіть у першому рядку мінімально можливий середній час (з точністю 5 знаків після десяткової крапки), який потрібно синам, щоб дістатись до міста призначення, не менше ніж з п'ятьма знаками післе десяткової крапки. У наступних k рядках виведіть шляхи синів, спочатку кількість доріг на шляху і потім номери доріг на шляху у тому порядку, у якому їх потрібно проходити. Дороги нумеруються, починаючи з одиниці, у тому порядку, у якому вони задані на вході.