הקיץ הלח והמחניק באזור החלב של ויסקונסין מעורר את צמא הפרות. Farmer John שואב מהרפת מים צלולים וקרים אל $N$ צינורות מסתעפים, $(3 \le N \le 99999)$, $N$ אי־זוגי, שמספריהם $1,\ldots,N$. חום הקיץ מחמם את המים הזורמים. Bessie מחפשת את הקרים ביותר כדי ליהנות ממזג האוויר יותר מכל פרה אחרת.

מפת כל הצינורות היא עץ ששורשו בחווה, ובכל הסתעפות בדיוק שני צינורות יוצאים. במפתיע כל צינור באורך יחידה אחת בדיוק; כל $N$ מחוברים איכשהו לעץ.

לפי המפה רשמו את המרחק מהרפת לכל הסתעפות וקצה. Bessie תחפש ברשימה את המים הקרים ביותר.

קצה צינור עשוי להיכנס להסתעפות או להיות ברז ונקרא במספר הצינור. במפה $C$ חיבורים, $(1 \le C \le N)$, בכל אחד שלושה שלמים: קצה $E_{i}$, $(1 \le E_{i} \le N)$, וצינורות $B1_{i}$, $B2_{i}$, $(2 \le B1_i \le N; 2 \le B2_i \le N)$. צינור $1$ מחובר לרפת וקצהו במרחק $1$.

קלט

• שורה $1$: שלמים $N$, $C$ מופרדי רווח.

• שורות $2,\ldots,C+1$: שורה $i+1$ מתארת הסתעפות $i$ בשלושה שלמים מופרדי רווחים: $E_{i}$, $B1_{i}$, $B2_{i}$.

פלט

• שורות $1,\ldots,N$: שורה $i$ מכילה שלם שהוא המרחק מהרפת לקצה צינור $i$.

דוגמאות

קלט 1

5 2
3 5 4
1 2 3

פלט 1

1
2
2
3
3

הערה

הקלט מתאר את המפה הבאה:

                    +------+
                    | רפת |
                    +------+
                       | 1
                       *
                    2 / \ 3
                         *
                      4 / \ 5

צינור $1$ תמיד במרחק $1$. $2$, $3$ מחוברים ישירות אליו ובמרחק $2$. $4$, $5$ מחוברים ל־$3$ ובמרחק $3$.

מחבר הבעיה: Rob Kolstad, 2008