يستعد 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