Module: خوارزمية ديكسترا

& nbsp؛

بعد أن اعتاد المصمم على القيام بأشياء مهمة في اللحظة الأخيرة ، أنهى التصميم قبل يومين من بدء المدرسة. سيستغرق الأمر يومًا آخر حتى تصنع الشركة المصنعة أكوابًا وتضع صورة عليها. يستغرق الناتو 24 ساعة فقط لنقل الأكواب من المصنع إلى LKSH.

& nbsp؛

لا يمكن بالطبع سحب طلب 10000000 كوب (أي هذا هو العدد الذي طلبه المنظمون) في رحلة واحدة. ومع ذلك ، بالنسبة للرحلة الأولى ، أريد أن أحضر أكبر عدد ممكن من الأكواب. تم طلب شاحنة ثقيلة واحدة للنقل. لكن هناك تحذير واحد: في بعض الطرق يوجد حد لوزن السيارة. لذلك ، إذا كانت السيارة محملة بأكواب في مقل العيون ، فقد لا يكون من الممكن استخدام أقصر طريق ، ولكن سيتعين عليك اتخاذ منعطف. قد يحدث حتى أنه بسبب هذا ، لن يكون لدى الشاحنة الوقت للوصول إلى المخيم في الوقت المحدد ، ولا يمكن السماح بذلك. إذن ، كم عدد الأكواب التي يمكن تحميلها في السيارة للحصول على الوقت لإحضار هذه البضائع القيمة في الوقت المحدد ، ودون انتهاك قواعد الطريق؟

يحتوي السطر الأول على الأرقام n (1 & le؛ n & le؛ 500) و m - عدد العقد في خريطة الطريق وعدد الطرق ، على التوالي. تحتوي سطور m التالية على معلومات حول الطرق. يتم وصف كل طريق في سطر منفصل على النحو التالي. أولاً ، يتم إعطاء أرقام نقاط الالتقاء المرتبطة بهذا الطريق ، ثم الوقت المستغرق للتنقل على طول هذا الطريق ، وأخيراً ، الحد الأقصى لوزن السيارة المسموح لها بالقيادة على هذا الطريق. من المعروف أن جميع الطرق تربط بين نقاط مختلفة ، ولكل زوج من النقاط يوجد طريق واحد على الأكثر يربطها مباشرة. جميع الأرقام مفصولة بمسافة واحدة أو أكثر. & nbsp؛

& nbsp؛

النقاط العقدية مرقمة من 1 إلى n. في الوقت نفسه ، يحتوي مصنع إنتاج الأكواب على رقم 1 و LKSH - رقم ن. يُحدد وقت السفر على الطريق بالدقائق ولا يتجاوز 1440 (24 ساعة). يُعطى حد الكتلة بالجرام ولا يتجاوز المليار. بالإضافة إلى ذلك ، من المعروف أن كوبًا واحدًا يزن 100 جرام ، وشاحنة فارغة - & nbsp؛ 3 طن.

& nbsp؛

الإخراج

اطبع رقمًا واحدًا - أقصى عدد من الأكواب التي يمكن إحضارها في الرحلة الأولى ، لن تستغرق أكثر من 24 ساعة.

أمثلة <الجسم>

#	إدخال	الإخراج
1	3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099	2