Farmer John מכין מסע למשלוח חבילה אל Farmer Dan. לשמירת השלום הוא נותן חטיף לכל פרה שפוגש בדרך. הוא חסכן מאוד ורוצה לפגוש כמה שפחות פרות.

במפה $N$ רפתות ($1 \le N \le 50,000$), מחוברות ב־$M$ שבילים דו־כיווניים ($1 \le M \le 50,000$), בכל אחד $C_{i}$ פרות מטיילות ($0 \le C_{i} \le 1,000$). שביל מחבר רפתות שונות $A_{i}$ ו־$B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$). בין שתי רפתות ייתכנו כמה שבילים ישירים. FJ ברפת 1 ו־Farmer Dan ברפת $N$.

התבוננו במפה:

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3

המסלול הטוב ביותר הוא 1 → 2 → 4 → 5 → 6 ועולה 1 + 0 + 3 + 1 = 5 חטיפים.

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

קלט

• שורה 1: השלמים $N$ ו־$M$ מופרדים ברווח.
• שורות $2..M+1$: השלמים $A_{i}$, $B_{i}$ ו־$C_{i}$ מופרדים ברווחים.

פלט

• שורה 1: מספר החטיפים המזערי הדרוש.

דוגמאות

קלט 1

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

פלט 1

5

מחבר הבעיה: Damon Doucet, 2011