Problem

11 /14


الاختصار (AB)

Problem

يتم إعطاؤك وصفًا لشبكة الطرق في الدولة. مهمتك - أوجد أقصر طريق بين المدينتين أ و ب.

إدخال
ترد شبكة الطرق في ملف الإدخال على النحو التالي: يحتوي السطر الأول على الأرقام N و K (1 & lt ؛ = N & lt ؛ = 100000 ، 0 & lt ؛ = K & lt ؛ = 300000) ، حيث K & ndash ؛ عدد الطرق. يحتوي كل سطر من سطور K التالية على وصف للطريق ذي الاتجاهين & ndash؛ ثلاثة أعداد صحيحة ai و bi و li (1aibiN، 1li106). هذا يعني أن هناك طريقًا بطول لي يؤدي من مدينة ai إلى مدينة ثنائية. يحتوي السطر الأخير على رقمين A & nbsp؛ و B & nbsp؛ & ndash؛ عدد المدن التي من الضروري حساب أقصر مسافة بينها (1 & lt ؛ = A ، B & lt ؛ = N)

بصمة
يجب إخراج رقم واحد & ndash؛ المسافة بين المدن المطلوبة. إذا كان من المستحيل الانتقال من & nbsp؛ city A إلى City B عن طريق البر ، اطبع & ndash؛ 1.

أمثلة <الجسم>
# إدخال الإخراج
1 6 4
1 2 7
2 4 8
4 5 1
4 3100
3 1 		115

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!