Rak

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

W Bajtocji niedawno zbudowano staw, w którym mieszka n żółwi. W każdym z n domków, ponumerowanych od 1 do n, które się tam znajdują, mieszka dokładnie jeden żółw. W najbliższym czasie do Bajtocji planuje wpaść w odwiedziny rak Wędrownik mieszkający na co dzień w Bajtomeryce. Jest on rakiem bardzo towarzyskim i wszystkie bajtockie żółwie są jego przyjaciółmi. Podczas swojego pobytu, Wędrownik chce się zatrzymać w domku u jednego z nich. Tu powstaje jednak dylemat - w którym domku powinien mieszkać?

Wędrownika interesują przede wszystkim takie domki, z których mógłby odwiedzać jak najwięcej przyjaciół. Mogłoby się wydawać, że odwiedzanie przyjaciół to żaden problem, ale jednak w bajtockim stawie jest to w pewien sposób utrudnione. Po pierwsze, aby kogoś odwiedzić, trzeba się najpierw dostać do jego domku. Po drugie, trzeba później wrócić z powrotem. Zakładamy również, że Wędrowiec nie odwiedza żółwia, u którego mieszka.

Wędrowiec porusza się zgodnie z następującymi zasadami:

  1. Między domkami można się przemieszczać jedynie po wyznaczonych trasach.
  2. Każda z tras jest jednokierunkowa i łączy dwa różne domki. Może istnieć kilka tras łączących te same domki.
  3. Rak może się poruszać na dwa sposoby - normalnie lub wspak. Jeśli w danym momencie rak porusza się normalnie i znajduje się w domku A, to może przejść do domku B, jeśli istnieje trasa prowadząca z A do B. Jeśli porusza się wspak, to może przejść z A do B tylko po trasie prowadzącej z B do A.
  4. Niektóre trasy są specjalne. Jeśli rak przejdzie taką trasą, to zaraz po tym rak zmienia swój sposób poruszania - jeśli chodził normalnie, to odtąd chodzi wspak, a jeśli chodził wspak, to będzie chodził normalnie.
  5. Idąc w odwiedziny, Wędrownik wychodzi ze swojego miejsca zamieszkania, poruszając się wspak. W czasie pobytu u przyjaciela rak nie zmienia swojego sposobu poruszania się. W momencie powrotu do domu Wędrownik musi się poruszać wspak (jeśli ostatnia trasa jest specjalna, to przed wejściem na nią powinien był poruszać się normalnie).

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia opis tras łączących domki w bajtockim stawie,
  • dla każdego domku obliczy ilość przyjaciół, których mógłby odwiedzać Wędrowiec, gdyby zamieszkał w tym domku,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite n i m (1 <= n <= 10.000, 1 <= m <= 100.000), oznaczające odpowiednio ilość domków i ilość tras. W kolejnych m wierszach znajdują się opisy poszczególnych tras, po jednym w każdym wierszu. Opis trasy składa się z trzech liczb a, b i s (1 <= a,b <= n, s równe 0 lub 1). Liczba a to numer domku, w którym trasa się zaczyna, b to numer domku, w którym się kończy. Trasa jest specjalna, jeśli s=1.

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie n wierszy. W i-tym z nich powinna się znaleźć liczba przyjaciół, których mógłby odwiedzić Wędrowiec, gdyby mieszkał w domku numer i.

Przykład

Dla danych wejściowych:

5 5
2 1 1
2 3 0
3 4 0
4 2 0
5 3 1

poprawnym wynikiem jest:

3
3
3
3
0

Mieszkając w domku numer 1 rak może odwiedzić przyjaciół w domkach 2, 3, 4. Mieszkając w domku numer 2 rak może odwiedzić przyjaciół w domkach 3, 4, 5. Mieszkając w domku numer 3 rak może odwiedzić przyjaciół w domkach 2, 4, 5. Mieszkając w domku numer 4 rak może odwiedzić przyjaciół w domkach 2, 3, 5. Mieszkając w domku numer 5 rak nie może odwiedzić żadnego przyjaciela.