Bessie עברה לחווה קטנה ולפעמים חוזרת לבקר אחת מחברותיה הטובות. היא אוהבת את הנוף ולא רוצה להגיע מהר לביתה הישן, לכן בוחרת מסלול שני קצר ביותר. היא יודעת שהוא קיים.

יש $R$ דרכים דו־כיווניות ($1 \le R \le 100,000$), כל אחת מחברת שניים מ־$N$ הצמתים ($1 \le N \le 5000$), הממוספרים $1..N$. מתחילה ב־1, והחברה והיעד ב־$N$.

המסלול השני יכול לחלוק דרכים עם כל קצר ביותר ולחזור, להשתמש באותה דרך או צומת שוב. הוא הקצר מבין הארוכים מהקצרים ביותר. אם יש כמה קצרים ביותר, הוא ארוך מהם אבל לא מכל מסלול אחר.

קלט

שורה 1: שני שלמים ברווח, $N$ ו־$R$.

שורות $2..R+1$: שלושה שלמים ברווח $A$, $B$, $D$, דרך בין $A$ ל־$B$ באורך $D$ ($1 \le D \le 5000$).

פלט

שורה 1: אורך המסלול השני הקצר ביותר מ־1 ל־$N$.

דוגמאות

קלט 1

4 4
1 2 100
2 4 200
2 3 250
3 4 100

פלט 1

450

הערה

רמז

שני מסלולים: $1 \to 2 \to 4$ (אורך $100+200=300$) ו־$1 \to 2 \to 3 \to 4$ (אורך $100+250+100=450$).