يتفقد Farmer John الأبقار بأمانة كل يوم. يسلك بعض المسارات البالغ عددها $M$ $(1 \le M \le 50,000)$ والمرقمة $1,\ldots,M$ من المرعى $1$ حتى المرعى $N$ (وهذه الرحلة ممكنة دائمًا في خرائط المسارات المقدمة في بيانات الاختبار). المراعي في مزرعة Farmer John وعددها $N$ $(1 \le N \le 10,000)$ ومرقمة $1,\ldots,N$ متصلة حاليًا بمسارات ترابية ثنائية الاتجاه. يصل كل مسار $i$ بين المرعيين $P1_{i}$ و$P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$، ويستغرق اجتيازه $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ وحدة زمنية.

يريد تجديد بعض مسارات مزرعته لتوفير الوقت في رحلته الطويلة. تحديدًا، سيختار $K$ $(1 \le K \le 20)$ مسارًا لتحويلها إلى طرق سريعة، مما يخفض فعليًا زمن اجتياز كل منها إلى $0$. ساعد FJ على تحديد المسارات التي يجددها لتقليل زمن الوصول من المرعى $1$ إلى $N$.

الإدخال

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

• الأسطر $2,\ldots,M+1$: يصف السطر $i+1$ المسار $i$ بثلاثة أعداد صحيحة تفصل بينها مسافات: $P1_{i}$ و$P2_{i}$ و$T_{i}$.

الإخراج

• السطر 1: طول أقصر مسار بعد تجديد ما لا يزيد على $K$ حافة.

أمثلة

الإدخال 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

الإخراج 1

1

ملاحظة

قيمة $K$ هي $1$؛ جدد المسار $3->4$ ليصبح زمنه $0$ بدلًا من $100$. أقصر مسار جديد هو $1->3->4$، وأصبح مجموع زمن اجتيازه $1$.

مؤلف المسألة: Percy Liang، 2008