Octagon אחראי למתקנים רבים בעלי חשיבות אסטרטגית, כגון ממגורות טילים, מכ״מים, חדרי אוכל, משרדים לוותיקי צבא, מחסני מדים, … חשוב ביותר לאבטח את רשת החיבורים בין המתקנים האלה, אך מצד שני יש למזער את האיום על הרשת. לכל כביש דו־כיווני המקשר בין מתקנים שונים נקבע מקדם איום מתקיפה (המכונה בקיצור המקדם). Johnny, שהחל לעבוד לאחרונה ב־Octagon, מסוגל גם באמצע הלילה לחשב תת־קבוצה של כבישים הממזערת את סכום המקדמים ועדיין מאפשרת לנוע בין כל זוג מתקנים; נכנה כביש השייך לפחות לתת־קבוצה אחת כזאת כביש מפתח.

אולם אין לקחת דבר כמובן מאליו: המקדמים עשויים להשתנות. כחלק מההערכה השנתית החליט Octagon לחשב לכל כביש את הערך הגדול ביותר של $x$ שעבורו, אם קובעים את המקדם שלו ל־$x$ (ומשאירים את כל המקדמים האחרים כפי שהיו), הכביש הוא כביש מפתח. המשימה הוטלה על Johnny, שאינו יכול לטעות בעניין חשוב כל כך.

קלט

השורה הראשונה של הקלט מכילה שני מספרים שלמים $n$ ו־$m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), המופרדים ברווח יחיד ומציינים בהתאמה את מספר המתקנים שבפיקוח Octagon ואת מספר הכבישים הדו־כיווניים ביניהם. המתקנים ממוספרים במספרים טבעיים עוקבים מ־$1$ עד $n$.

בכל אחת מ־$m$ השורות הבאות יש שלושה מספרים שלמים: $a$, $b$ ו־$c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), המופרדים ברווח יחיד ומתארים כביש דו־כיווני בין המתקנים $a$ ו־$b$ שמקדם שלו הוא $c$. כל זוג לא סדור $\{a,b\}$ מופיע לכל היותר פעם אחת.

הכבישים הקיימים תמיד מאפשרים לנוע בין כל שני מתקנים.

פלט

יש להדפיס $m$ שורות, אחת לכל כביש בקלט, באותו סדר שבו הכבישים נתונים בקלט. בשורה המתאימה לכביש מסוים יש להדפיס מספר טבעי אחד: הערך המרבי שעבורו, לאחר שינוי מקדם הכביש לערך זה (והשארת המקדמים האחרים ללא שינוי), הכביש הוא כביש מפתח. אם ערך זה גדול מ־$10^9$ או יכול להיות גדול כרצוננו, יש להדפיס $10^9$.

דוגמאות

קלט 1

6 7
1 2 2
2 3 1
3 4 0
1 4 3
3 5 20
4 5 8
3 6 14

פלט 1

3
3
3
2
8
20
1000000000

הערה

רשת הכבישים מהדוגמה נראית כך: