اشترى مصنع 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