Module: برمجة الرسم البياني الديناميكي

Problem

تذهب En إلى غابة الفطر لجمع الفطر.

توجد مسارات متجهة في غابة الفطر تربط ن الأشجار. ينمو الفطر في كل طريق. عندما يسير En على طول الطريق ، يلتقط كل الفطر على ذلك الطريق. ومع ذلك ، فإن غابة الفطر بها تربة خصبة بحيث ينمو الفطر بمعدل رائع. ينمو الفطر الجديد بمجرد أن ينتهي En من قطف الفطر على المسار. وبالتحديد ، بعد مرور En على طول المسار للمرة الأولى ، ينمو عدد أقل من الفطر عما كان عليه قبل هذا المقطع. وبالتالي ، إذا كان المسار يحتوي في البداية على x عيش الغراب ، فسيجمع En x فطرًا في الممر الأول ، x & thinsp ؛ - & thinsp؛ 1 فطر في الثاني ، x & thinsp ؛ - & thinsp؛ 1 & thinsp ؛ - & thinsp؛ 2 فطر في الثالث ، وهكذا على. ومع ذلك ، لا يمكن أن يكون عدد الفطر أقل من 0.
على سبيل المثال ، دع 9 عيش الغراب تنمو على الطريق. ثم عدد الفطر الذي سيجمعه En هو 9 و 8 و 6 و 3 للممرات من واحد إلى أربعة. بدءًا من التمريرة الخامسة فصاعدًا ، لن يتمكن En من جمع أي شيء من هذا المسار (ولكن لا يزال بإمكانه السير عليه).

قرر En أن يبدأ من الشجرة s. ما هو الحد الأقصى لعدد الفطر الذي يمكن أن يجمعه بالتحرك فقط على طول المسارات الموصوفة؟

الإدخال:
يحتوي السطر الأول على عددين صحيحين n و m (1 & thinsp؛ & le؛ & thinsp؛ n & thinsp؛ & le؛ & thinsp؛ 300000، 0 & thinsp؛ & le؛ & thinsp؛ m & thinsp؛ & le؛ & thinsp؛ 300000) & mdash؛ عدد الأشجار وعدد المسارات الموجهة في غابة الفطر على التوالي.
يحتوي كل سطر من سطور m التالية على ثلاثة أعداد صحيحة x و y و w (1 & thinsp؛ & le؛ & thinsp؛ x، & thinsp؛ y & thinsp؛ & le؛ & thinsp؛ n، 0 & thinsp؛ & le؛ & thinsp؛ w & thinsp؛ & le؛ & thinsp؛ 10 ⁸ ) يصف المسار الذي يؤدي من الشجرة x إلى الشجرة y مع w عيش الغراب في البداية. هناك مسارات تؤدي من شجرة إلى نفس الشجرة ، بالإضافة إلى العديد من المسارات التي تربط نفس زوج الأشجار.
يحتوي السطر الأخير على عدد صحيح واحد s (1 & thinsp؛ & le؛ & thinsp؛ s & thinsp؛ & le؛ & thinsp؛ n) & mdash؛ موضع البداية En.

الإخراج:
طباعة عدد صحيح واحد و [مدش] ؛ أقصى عدد من الفطر الذي يمكن أن تجمعه إن في طريقها.

أمثلة:
نبسب ؛ <الجسم>

إدخال	الإخراج
2 2 1 2 4 2 1 4 1	16
3 3 1 2 4 2 3 3 1 3 8 1	8

التفسيرات:
في المثال الأول ، يمكن لـ En أن يتجول في الدائرة ثلاث مرات ويجمع 4 & thinsp؛ + & thinsp؛ 4 & thinsp؛ + & thinsp؛ 3 & thinsp؛ + & thinsp؛ 3 & thinsp؛ + & thinsp؛ 1 & thinsp؛ + & thinsp؛ 1 & thinsp؛ = & thinsp؛ 16 mushrooms. بعد ذلك ، لن يكون هناك فطر ليجمعه En.
في المثال الثاني ، يمكن لـ En الانتقال إلى الشجرة 3 واختيار 8 فطر على المسار من الشجرة 1 إلى الشجرة 3.