Këbab
Limit pamięci: 128 MB
Bajtazar jest redaktorem nowego portalu internetowego poświęconego
gastronomii w Bajtogrodzie.
Wymyślił właśnie temat, który, jeśli zostanie rzetelnie opracowany,
może znacząco zwiększyć popularność serwisu.
Mianowicie, Bajtazar wpadł na pomysł stworzenia rankingu
bajtogrodzkich barów serwujących këbaby.
W Bajtogrodzie jest skrzyżowań, ponumerowanych
liczbami od do .
Skrzyżowania połączone są dwukierunkowymi
drogami o różnych długościach.
Wiadomo, że między dowolnymi dwoma skrzyżowaniami można przejechać
na dokładnie jeden sposób.
Przy każdym skrzyżowaniu znajduje się dokładnie
jeden bar z këbabami.
Ponieważ w każdym lokalu kucharze serwują równie smaczne i tanie këbaby,
to rozstrzygającym kryterium w rankingu stał się koszt dowozu posiłku
do klienta.
Bajtazar zebrał dokładne informacje na temat barów
i zanotował, że lokal przy -tym skrzyżowaniu dostarcza
posiłki bezpłatnie tylko do skrzyżowań odległych
od niego o nie więcej niż .
Początkowo założył, że najwięcej punktów w kategorii
"dostawa" otrzyma ten dostawca, który dojeżdża najdalej.
Wkrótce zmienił jednak zdanie, gdyż słusznie
zauważył, że znacznie lepiej oceniać
lokale po liczbie skrzyżowań, do których këbab może być dostarczony
z lokalu bezpłatnie.
Twoim zadaniem jest znaleźć tę liczbę dla każdego lokalu.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita
() oznaczająca liczbę skrzyżowań w Bajtogrodzie.
W drugim wierszu znajduje się liczb całkowitych
()
oznaczających maksymalne odległości
przy bezpłatnej dostawie dla kolejnych barów.
W -tym z kolejnych wierszy znajdują się trzy liczby
całkowite (),
oznaczające, że skrzyżowania i są połączone
drogą o długości .
W testach wartych punktów zachodzi warunek .
W testach wartych punktów istnieje co najwyżej jedno skrzyżowanie,
z którego wychodzą więcej niż dwie ulice. Dodatkowo w tych testach zachodzi
warunek .
Wyjście
Na wyjście należy wypisać wierszy; w -tym z nich
powinna znaleźć się liczba skrzyżowań, do których
-ty bar z këbabami dostarcza jedzenie bezpłatnie.
Przykład
Dla danych wejściowych:
5
2 3 3 6 5
1 2 2
2 3 1
3 4 3
4 5 2
poprawną odpowiedzią jest:
2
3
4
5
3
Zadanie(utrudnione) zapożyczone z USACO DEC12.