问题 H: traffic

Alice's country has $n$ cities, and these $n$ cities are connected by $n+1$ channels. If a channel is opened, residents on one end can reach the other end through this channel. There are a total of T+1T+1T+1 days (from day $0$ to day $T$), and the cost of opening the $i$-th channel on the $j$-th day is given by the expression ai×j+bia_i \times j + b_iai×j+bi. The total cost for a specific day is the sum of costs of all the channels opened on that day.

Alice needs to determine which channels to open each day to ensure that residents can reach any other city through the opened channels every day while minimizing the total cost. Can you help her?

The first line contains two integers $n$ and T(2≤n,T≤105)T (2 \leq n, T \leq 10^5)T(2≤n,T≤105), representing the number of cities and the total number of days.
The next $n+1$ lines (from $2$nd to $(n+2)$-th) each contain four integers ui,vi,ai,bi(1≤ui,vi≤n,0≤ai,bi≤108)u_i, v_i, a_i, b_i(1 \leq u_i, v_i \leq n, 0 \leq a_i,b_i \leq 10^8)ui,vi,ai,bi(1≤ui,vi≤n,0≤ai,bi≤108), representing a channel between cities uiu_iui and viv_ivi. The cost of opening this channel on the $j$-th day is ai×j+bia_i \times j + b_iai×j+bi.
It is guaranteed that there are no self-loops, but there may be multiple edges between the same pair of vertices.

Output T+1T+1T+1 lines, each containing an integer, representing the minimum cost for each of the days from $0$ to $T$.

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

6
12
16
20