يريد Farmer John تركيب خط هاتف في مزرعته. لكن شركة الهاتف لا تتعاون، ولذلك عليه دفع ثمن بعض الكابلات اللازمة لتوصيل المزرعة بشبكة الهاتف.

توجد $N$ أعمدة هاتف وحيدة، $(1 \le N \le 1,000)$، متناثرة في أرضه ومرقمة للتيسير $1..N$؛ ولا تصل بينها أي كابلات. يمكن توصيل $P$ أزواج من الأعمدة، $(1 \le P \le 10,000)$، بكابل؛ أما البقية فبعيدة جداً عن بعضها.

يمكن للكابل ذي الفهرس $i$ وصل العمودين المختلفين $A_i$ و$B_i$، ويكون طوله عند استخدامه $L_i$ وحدة، $(1 \le L_i \le 1,000,000)$. لا تذكر بيانات الإدخال أي زوج {$A_i,B_i$} أكثر من مرة. العمود $1$ موصول بالفعل بشبكة الهاتف، والعمود $N$ في المزرعة. يجب توصيل العمودين $1$ و$N$ بمسار كابلات؛ ويمكن استخدام الأعمدة الأخرى أو عدم استخدامها.

اتضح أن الشركة مستعدة لتزويد Farmer John بعدد $K$ من الكابلات مجاناً، $(0 \le K < N)$. وبعد ذلك عليه دفع سعر يساوي طول أطول كابل متبقٍ يحتاجه (يُوصل كل زوج أعمدة بكابل مستقل)، أو $0$ إذا لم يحتج إلى كابلات إضافية.

حدد أقل مبلغ يجب أن يدفعه Farmer John.

الإدخال

اقرأ البيانات من الإدخال القياسي.

• السطر 1: ثلاثة أعداد صحيحة تفصل بينها مسافات: $N$ و$P$ و$K$.

• الأسطر $2..P+1$: يحتوي السطر $i+1$ على ثلاثة أعداد صحيحة تفصل بينها مسافات: $A_i$ و$B_i$ و$L_i$.

الإخراج

اكتب الناتج إلى الإخراج القياسي.

• السطر 1: عدد صحيح واحد، وهو أقل مبلغ يستطيع Farmer John دفعه. إذا استحال توصيل المزرعة بالشركة، اطبع $-1$.

أمثلة

الإدخال 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

الإخراج 1

4

ملاحظة

توجد 5 أعمدة. لا يمكن توصيل العمود $1$ مباشرة بالعمود $4$ أو $5$. ولا يمكن توصيل العمود $5$ مباشرة بالعمود $1$ أو $3$. يمكن توصيل جميع الأزواج الأخرى. ستوفر الشركة كابلاً مجانياً واحداً.

إذا وصلنا العمود $1$ بالعمود $3$، و$3$ بالعمود $2$، و$2$ بالعمود $5$، فإن Farmer John يحتاج كابلات بأطوال $4$ و$3$ و$9$. ستوفر الشركة الكابل ذي الطول $9$، فيكون طول أطول كابل متبقٍ مطلوب $4$.

مؤلف المسألة: Paul Christiano، 2007