asfalt

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 indreaptă 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 încat lungimea rutei de la oraşul $S$ la orasul $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 asfalt.in se află patru numere $N$, $M$, $S$ şi $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 asfalt.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 din drumurile ce trebuie mărite.

Restricții și precizări

• $1 \leq N \leq 500$
• $1 \leq M \leq 5 \ 000$
• $1 \leq c \leq 10^6$
• $1 \leq x, y \leq N$
• orice soluţie ce are un număr minim de drumuri este acceptată
• nu vor exista mai multe drumuri între două oraşe

Exemplu

asfalt.in

4 4 1 4
1 2 1
1 3 2
2 4 2
3 4 1

asfalt.out

2
1 2
1 3