Рабочее место участника

Однажды, в 2111 году, на съезде межгалактической футбольной федерации единогласно решили доверить право на проведение в 2118 году чемпионата вселенной по футболу Берляндскому футбольному союзу. И вот на долю мэра Берляндска пала нелегкая доля по организации такого масштабного события у себя в городе. И главная проблема, которая перед ним встала, заключается не в постройке стадионов, а в подготовке инфраструктуры: транспорта, гостиниц, системы общественного питания. Вам же необходимо помочь ему с решением проблемы постройки метро в Берляндске.

Болельщики из определенной галактики могут ездить только на удобном для них виде составов метро. Для того, чтобы гости остались довольны, необходимо сделать на перегонах между станциями метро специальные составы. У каждой галактики есть свой уникальный тип состава, ездящий по своим уникальным рельсам и только по ним.

Про каждый перегон между двумя станциями метро известно, какого он типа (болельщики из какой галактики должны по нему ездить). Было решено, что будет куплено минимальное возможное количество составов метро, при котором через каждую станцию будут курсировать составы всех типов, для которых из этой станции есть подходящий перегон. Если состав курсирует через некоторую станцию метро А, то он курсирует также через все станции, до которых можно добраться из А по перегонам подходящего типа. Вам необходимо определить, сколько необходимо купить составов каждого типа.

В первой строке входного файла даны три целых числа `n`, `m` и `k` (`1\ ≤\ n\ ≤\ 10^5`, `1\ ≤\ m\ ≤\ 2*10^5`, `1\ ≤\ k\ ≤\ 10^5`) – количество станций метро, количество перегонов между ними и количество типов составов.

В следующих `m` строках описаны перегоны, по одному в строке. Каждый перегон описан тремя числами: номера станций метро, которые соединяет этот туннель, и номер типа состава, который может проехать по этому перегону. Номера станций – положительные числа, не превышающие `n`. Тип состава – положительное число, не превышающее `m`.

Выходной файл должен состоять из `k` строк.

В `i`-ой строке выведите количество составов типа `i`, которое необходимо купить.

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

2 
1