تتولى 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

ملاحظة

تبدو شبكة الطرق في المثال كما يلي: