Problem C
Tågmani

Det är väldigt välkänt att Julia gillar serien På spåret. Då kanske det inte kommer som en överraskning att hon gillar att åka tåg. Tyvärr har hon nyligen spårat ur lite, och denna tidigare oskyldiga hobby har förvandlats till ett maniskt behov att åka tåg. Problemet är att det är svårt att åka tåg så mycket som hon skulle vilja, eftersom resorna tar lång tid. Även om hon inte kan åka med alla tåg, så försöker hon resa med så många som möjligt. Efter att hon suttit timtals i sitt rum och försökt skapa den bästa reseplanen bestämmer du dig för att hjälpa henne. Även om mängden tåg hon åker inte är hälsosamt, så föredrar du att hon får åka tåg istället för att planera sin tågåkning.

Julia bor i staden Lönnköping. Lönnköping har $N$ stationer numrerade från $1$ till $N$. För att resa mellan dessa finns det två transportmedel: elscootrar och tåg. Det finns så många elscootrar i staden att hon kan påbörja en resa på elscooter från vilken station som helst. Hon kan bara åka elscooter längs med de $N-1$ vägarna i staden. Man kan färdas från vilken station till vilken annan station som helst endast genom att använda en eller flera av dessa vägarna, alltså utgör vägnätverket ett träd. Det tar ett visst antal sekunder att färdas längs med varje väg med scooter.

Hon kan även färdas med de $K$ nästkommande tågavgångarna. Varje tåg har ett strikt schema: det avgår från en viss station vid en viss tid, och anländer vid dess slutstation efter ett antal sekunder. Om Julia befinner sig vid en station samma sekund som ett tåg avgår kan hon åka med det om hon vill. Hon åker då med tåget till dess slutstation (hon kan inte förmå sig att stiga av ett tåg innan hon verkligen måste). Om ett tåg anländer vid en station samma sekund som ett annat avgår hinner hon göra bytet om hon så vill.

Givet hur vägnätverket ser ut och de $K$ nästa tågavgångarna, hur många tåg kan Julia åka med om hon planerar sin resa optimalt? Eftersom planen är en bit in i framtiden är hon inte säker på var hon ska börja, så hon vill att du beräknar största antalet tåg hon kan åka med för varje möjlig startstation. Du kan anta att hon alltid börjar sin resa vid tid $0$.

Indata

Den första raden i indatan innehåller två heltal, $N$ och $K$ ($1 \le N, K \le 10^5$), antalet hållplatser det finns i Lönnköping och antalet tågavgångar som du ska betrakta.

De följande $N-1$ raderna beskriver vägnätverket. Vardera av dessa rader innehåller heltalen $u,v,s$ ($1 \leq u, v \leq N$, $1 \leq s \leq 10^9$), som betyder att det finns en väg mellan stationerna med nummer $u$ och $v$. Det tar $s$ sekunder att åka från $u$ till $v$ eller $v$ till $u$ med vägen om man använder en elscooter.

Därefter följer $K$ rader som beskriver tågavgångarna. Vardera av dessa rader innehåller heltalen $u,v,t,d$ ($1 \leq u,v \leq N$, $u \neq v$, $1 \leq t, d \leq 10^9$), vilket betyder att vid $t$ så avgår det ett tåg från station $u$ till station $v$, som anländer vid station $v$ vid tid $t+d$. Det är garanterat att alla $t$ är unika.

Utdata

Låt $x_i$ beteckna maximala antalet tåg Julia kan åka med, ifall hon börjar sin resa vid station $i$. Skriv ut $x_1,x_2,\ldots ,x_N$ separerade med mellanslag.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

3 3
1 2 1
2 3 1
1 3 0 1
1 3 3 2
1 3 6 1

2 1 1