โรงงานของ Little Q เพิ่งซื้ออุปกรณ์ใหม่ $n$ เครื่อง โดยมีหมายเลข $1,2,\ldots,n$

ในโรงงานมีคนงาน $n$ คน โดยมีหมายเลข $1,2,\ldots,n$ คนงานแต่ละคนสามารถได้รับมอบหมายให้อุปกรณ์ได้ไม่เกินหนึ่งเครื่อง และอุปกรณ์แต่ละเครื่องจะมอบหมายให้คนงานหลายคนไม่ได้ หาก Little Q มอบหมายคนงานคนที่ $i$ ให้อุปกรณ์เครื่องที่ $j$ จะได้กำไร $p_{i,j}$ อย่างไรก็ตาม คนงานเหล่านี้ยังไม่มีประสบการณ์มากนัก ดังนั้นค่าในเมทริกซ์ $p$ ส่วนใหญ่จึงเป็นศูนย์ ยกเว้น $m$ ช่อง โดยจะให้ข้อมูลของ $m$ ช่องนี้มา

สำหรับทุกค่า $k$ ($1\le k\le n$) จงหาคู่คนงานกับอุปกรณ์จำนวน $k$ คู่ แล้วมอบหมายคนงานให้อุปกรณ์เหล่านั้น โดยทำให้กำไรรวมของ $k$ คู่นี้มีค่ามากที่สุด

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีกรณีทดสอบเพียงกรณีเดียว

บรรทัดแรกมีจำนวนเต็มสองจำนวน $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$) แทนจำนวนคนงาน/อุปกรณ์ใหม่ และจำนวนช่องพิเศษใน $p$

แต่ละบรรทัดใน $m$ บรรทัดถัดมามีจำนวนเต็มสามจำนวน $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$) แทน $p_{u_i,v_i}=w_i$ แต่ละคู่ $u_i,v_i$ จะถูกระบุไม่เกินหนึ่งครั้ง

ข้อมูลส่งออก

พิมพ์ $n$ บรรทัด โดยบรรทัดที่ $k$ ($1\le k\le n$) มีจำนวนเต็มหนึ่งจำนวน แทนกำไรรวมที่มากที่สุดที่เป็นไปได้สำหรับคู่คนงานกับอุปกรณ์จำนวน $k$ คู่

ตัวอย่าง

ข้อมูลนำเข้า 1

2 3
1 1 4
1 2 2
2 1 3

ข้อมูลส่งออก 1

4
5

ข้อมูลนำเข้า 2

2 3
1 1 5
1 2 2
2 1 2

ข้อมูลส่งออก 2

5
5