انتقلت 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$).