تعلّم الملياردير Christian اليوم خوارزمية Dijkstra مع جهود Johnson. أعجبته كثيرًا، فقرر إضافة جهود إلى جميع رسومه البيانية المفضلة. أذواق Christian غريبة جدًا؛ فهو لا يحتفظ في غرفته السرية إلا برسوم بيانية موجهة وموزونة.

لنتذكر كيف تعمل الجهود. يُسنَد إلى كل رأس $v$ جهد، وهو عدد حقيقي $\varphi(v)$. إذا كانت هناك حافة من $u$ إلى $v$ بوزن أصلي $w$، فإن وزنها الجديد سيكون $w'=w-\varphi(v)+\varphi(u)$.

تُعرَّف قوة الرسم البياني بأنها أصغر وزن بين أوزان حوافه. لا يريد Christian رسومًا بيانية ضعيفة في غرفته، لذا يريد اختيار الجهود بحيث تكون قوة الرسم البياني أكبر ما يمكن. ساعده في ذلك.

الإدخال

يحتوي السطر الأول على عددين صحيحين $n$ ($2\le n\le1000$) و$m$ ($1\le m\le100\,000$)، وهما عدد الرؤوس والحواف في الرسم البياني المفضل لدى Christian. يحتوي كل من الأسطر $m$ التالية على ثلاثة أعداد صحيحة $u_i,v_i,w_i$ تصف حافة: بدايتها ونهايتها ووزنها، على الترتيب ($1\le u_i,v_i\le n$، $|w_i|\le10^6$).

الإخراج

يجب أن يحتوي السطر الأول على أكبر قوة ممكنة للرسم البياني. إذا أمكن جعل الإجابة كبيرة بلا حد، فاطبع السلسلة «+inf» بدلًا منها.

إذا كانت الإجابة منتهية، فيجب أن يحتوي السطر الثاني على $n$ أعداد حقيقية، هي جهود الرؤوس. يجب ألا تتجاوز القيمة المطلقة لأي منها $10^{10}$. يجب ألا يختلف جوابك عن الجواب الصحيح، ولا عن الجواب المحسوب من الجهود التي تقدمها، بأكثر من $10^{-5}$.

أمثلة

الإدخال 1

3 3
1 2 1
2 3 1
3 1 1

الإخراج 1

1.0
0.0 0.0 0.0

الإدخال 2

2 1
1 2 1

الإخراج 2

+inf