Nhà máy của Little Q gần đây đã mua $n$ thiết bị mới, được đánh số $1,2,\ldots,n$.

Nhà máy có $n$ công nhân, được đánh số $1,2,\ldots,n$. Mỗi công nhân chỉ có thể được phân công cho tối đa một thiết bị, và không thiết bị nào được phân công cho nhiều công nhân. Nếu Little Q phân công công nhân thứ $i$ cho thiết bị thứ $j$, họ sẽ mang lại lợi nhuận $p_{i,j}$. Tuy nhiên, các công nhân này chưa có nhiều kinh nghiệm, nên hầu hết các giá trị trong ma trận $p$ bằng không, ngoại trừ $m$ ô. Bạn sẽ được cho $m$ ô này.

Với mỗi $k$ ($1\le k\le n$), hãy tìm $k$ cặp công nhân và thiết bị, rồi phân công các công nhân cho những thiết bị đó sao cho tổng lợi nhuận của $k$ cặp là lớn nhất.

Dữ liệu vào

Dữ liệu vào chỉ chứa một bộ kiểm thử.

Dòng đầu chứa hai số nguyên $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$), lần lượt là số công nhân/thiết bị mới và số ô đặc biệt trong $p$.

Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$), cho biết $p_{u_i,v_i}=w_i$. Mỗi cặp $u_i,v_i$ được mô tả nhiều nhất một lần.

Dữ liệu ra

In $n$ dòng, trong đó dòng thứ $k$ ($1\le k\le n$) chứa một số nguyên là tổng lợi nhuận lớn nhất có thể đạt được với $k$ cặp công nhân và thiết bị.

Ví dụ

Dữ liệu vào 1

2 3
1 1 4
1 2 2
2 1 3

Dữ liệu ra 1

4
5

Dữ liệu vào 2

2 3
1 1 5
1 2 2
2 1 2

Dữ liệu ra 2

5
5