המפעל של 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