Задача C. Упаковка схемы ≡

Автор:	Жюри всероссийских зимних сборов школьников 2007-2008		Ограничение времени:	2 сек
Входной файл:	schema.in		Ограничение памяти:	64 Мб
Выходной файл:	schema.out
Максимальный балл:	100

Условие

Схема состоит из нескольких узлов и соединений между ними. Для сохранности соединений схемы некоторые узлы помещают в отдельные коробки. Те соединения, которые полностью попадают в одну коробку, называются защищенными. В зависимости от нагрузки и важности, соединения изготавливают из различных сплавов, а, следовательно, их стоимость различна. Ваша задача — распределить узлы по k коробкам так, чтобы суммарная стоимость всех незащищенных соединений была минимальна. Каждая коробка должна содержать хотя бы один узел.

Формат входного файла

В первой строке входного файла записано три числа n, m, k — количество узлов, количество соединений и количество коробок соответственно. Далее в m строках записано описание соединений. Соединение задается тремя целыми числами x, y, z. Это означает, что узел x соединен с узлом y, а стоимость соединения z. Каждая пара узлов соединена не более, чем одним соединением.

Формат выходного файла

В выходной файл выведите n чисел. i-ое число означает номер коробки, в которую помещена i-ая вершина. Коробки нумеруются числами от 1 до k. В каждой коробке должен быть хотя бы один узел. Суммарная стоимость всех незащищенных соединений должна быть минимальна. Если существует несколько вариантов правильного ответа, выведите любой.

Ограничения

1 ≤ n ≤ 14

1 ≤ m ≤ n(n − 1)/2

1 ≤ k ≤ n

1 ≤ x, y ≤ n

x ≠ y

1 ≤ z ≤ 10⁷>

Примеры тестов

№	Входной файл (schema.in)	Выходной файл (schema.out)
1	3 3 2 1 2 100 2 3 200 3 1 300 скопировать	1 2 1 скопировать

---