Băştinaşii din insula BuruBuru tocmai au descoperit asfaltul, aşa că şi-au unit cele N sate (numerotate de la 1 la N) prin M drumuri bidirecţionale, fiecare de o lungime dată.
Văzând aceste progrese tehnologice, nişte colonişti au hotărât că vor să pună stăpânire pe insulă. Aceştia pleacă din satul cu indice S (locul unde au debarcat) şi se îndreaptă către capitala băştinaşilor, oraşul D, mergând pe ruta de lungime minimă (suma lungimilor drumurilor ce alcătuiesc ruta să fie minimă).
Cerinţă
Băştinaşii doresc să mai amâne atacul coloniştilor, aşa că ar vrea să ştie care este numărul minim de drumuri cărora trebuie să li se mărească lungimea cu cel puţin o unitate astfel încât lungimea rutei de la oraşul S la oraşul D să crească cu cel puţin o unitate. Deoarece băştinaşii încă nu au descoperit calculatorul, este de datoria voastră să îi ajutaţi!
Date de intrare
Pe prima linie a fişierului asfalt1.in se află patru numere N M S D cu semnificaţia de mai sus. Următoarele M linii conţin câte trei numere x y c fiecare, semnificând faptul că există un drum între oraşele x şi y de lungime c.
Date de ieşire
Fişierul asfalt1.out va conţine pe prima linie numărul minim de drumuri a căror lungime trebuie mărită. Următoarele linii vor conţine fiecare câte două numere naturale, reprezentând indicii oraşelor ce descriu unul dintre drumurile ce trebuie mărite.
Restricţii
• 1 <= N <= 500
• 1 <= M <= 5000
• 1 <= c <= 106
• 1 <= x, y <= N
• Orice soluţie ce are un număr minim de drumuri este acceptată. • Nu vor exista mai multe drumuri între două oraşe.