המיליארדר 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