إعطاء رسم بياني موجه يمكن أن يكون له حواف وحلقات متعددة. كل حافة لها وزن معبر عنه بعدد صحيح (ربما سالب). ويضمن عدم وجود دورات وزن سلبية.
أنت بحاجة إلى حساب أطوال أقصر المسارات من الرأس رقم 1 إلى جميع الرؤوس الأخرى.
& nbsp؛
إدخال
يتلقى البرنامج أولاً الرقم N (1 & lt؛ = N & lt؛ = 100) & ndash؛ عدد رؤوس الرسم البياني والرقم م (0 & lt ؛ = M & lt ؛ = 10000) & ndash ؛ عدد الضلوع. تحتوي الأسطر التالية على M ثلاثيات من الأرقام التي تصف الحواف: بداية الحافة ، ونهاية الحافة ، والوزن (الوزن & ndash ؛ هو عدد صحيح من -100 إلى 100).
& nbsp؛
الإخراج
يجب على البرنامج إخراج N أرقام & ndash؛ المسافات من الرأس رقم 1 إلى جميع رؤوس الرسم البياني. إذا لم يكن هناك مسار للرأس المقابل ، فقم بطباعة الرقم 30000 بدلاً من طول المسار.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
6 4
1 2 10
2 3 10
1 3100
4 5-10
|
0 10 20 30000 30000 30000 & nbsp؛ |