У всіх бувають погані дні. Можна коритись долі, а можна взяти все в свої руки. Саме така ситуація і відбувається зараз, клас вирушив у поїздку до Карпат. Клас розбився на групки, одна з цих групок розміру ~k~ друзі на думку класного керівника, але насправді терпіти одне-одного не можуть. Вони мусять зіграти в гру суть якої в тому щоб сидіти на ~k~ різних пеньках і передавати повідомлення по колу (тобто є якийсь порядок гравців починаючи з першого і гравець ~1~ передає гравцю ~2~, ~2~ — ~3~, ...., ~k-1~ — ~k~). Між пеньками є стежки по яким можна ходити щоб передати повідомлення, усього є ~n~ пеньків і ~m~ стежок, стежки можуть мати різну довжину (час проходження), повідомлення отримуються миттєво, час займає тільки проходження стежки. Потрібно знайти такий порядок пеньків що невдоволеність гравців буде мінімальною. Невдоволеність гравців — визначимо як добуток довжин стежок по яким пройде хоча б один гравець. Між двома сусідніми в порядку пеньками мусить існувати пряма стежка і гравець йтиме від свого пенька до наступного тільки по прямій стежці, якщо існує кілька таких стежок — по стежці мінімальної довжини.

Input

У першому рядку дані три числа: ~n~ ~m~ ~k~ - кількість доріг і кількість ребер і розмір группи; ~1 \le n,m \le 10^3~ , ~1 \le k \le 6~ У наступних ~m~ рядках дана інформація про стежки, по три числа: ~u~ ~v~ ~w~ - двухстороння стежка між пеньками з індексами ~u~ і ~v~ довжини ~w~; ~1\le u,v \le n~, ~1 \le w \le 100~

Output

У першому рядку виведіть мінімальну сумму невдоволеностей. У другому рядку виведіть індекси пеньків в порядку при якому досягається така сумма. Якщо існує кілька правильних відповідей - виведіть будь-яку. Якщо відповіді не існує — виведіть ~-1~.

Sample Input 1

3 3 3
1 2 1
2 3 4
3 1 4

Sample Output 1

4
3 2 1

Sample Input 2

3 2 4
1 2 1
2 3 4

Sample Output 2

-1

Sample Input 3

8 6 4
1 2 1
2 3 4
3 4 5
5 6 2
6 7 2
7 8 2

Sample Output 3

8
5 6 7 8

Sample Input 4

6 6 6
1 2 5
2 3 6
3 4 1
4 5 10
5 6 6
6 1 9

Sample Output 4

1620
4 3 2 1 6 5