Alice's country has cities, and these cities are connected by channels. If a channel is opened, residents on one end can reach the other end through this channel. There are a total of days (from day to day ), and the cost of opening the -th channel on the -th day is given by the expression . 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  and , representing the number of cities and the total number of days.

The next  lines (from nd to -th) each contain four integers , representing a channel between cities  and . The cost of opening this channel on the -th day is .

It is guaranteed that there are no self-loops, but there may be multiple edges between the same pair of vertices.

Output  lines, each containing an integer, representing the minimum cost for each of the days from  to .

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