الصيف الرطب الخانق بمنطقة الألبان في ويسكونسن يدفع الأبقار لإرواء عطشها. يضخ 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