Kompanija NishT el trenutno ugrađuje širom zemlje svoj najnoviji hit - brze jednosmerne međugradske telefnoske linije. Do sada su napravili m jednosmernih linija između nekih od n gradova. Svaka linija povezuje neka dva grada i ukoliko postoji linija od grada A do grada B, tada je preko nje moguće iz grada A zvati grad B ali ne i obratno (to je jedna od mana sistema ali linije su mnogo jeftinije od starih, a to je ono što je bitno). Svaku jednosmernu telefonsku liniju karakteriše jedan broj t_i - vreme (u mikrosekundama) potrebno da se uspostavi veza između odgovarajućih gradova.
Grad A može da zove grad B i indirektno, ako postoji neki niz gradova, gde je A prvi, a B poslednji, i između svaka dva uzastopna grada postoji telefonska linija u odgovarajućem smeru. Tada je vreme za uspostavljanje veze između A i B jednako zbiru vremena za uspostavlja nje svih međuveza na putu. Ukoliko postoji više načina da se uspostavi veza između neka dva grada, operateri uvek biraju onaj kod koga je vreme uspostavljanja minimalno.

Poznato je da NishTel ima centre u dva grada (NishB i ABNish) kao i da je iz svakog od ta dva grada moguće zvati (direktno ili indirektno) bilo koji drugi grad. Takođe je poznato da je NishTel zapao u dugove i da mora da sruši neke od m linija koje su postavili. Oni žele da sruše što više linija ali tako da minimalna vremena potrebna za uspostavljanje veza od gradova NishB i ABNish do svakog od ostalih gradova ostanu ista (uključujući i vremena između dva centra). Pomozite NishTel-u da ispuni svoj plan i spase se stečaja.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalaze se 4 prirodna broja n, m, A i B koji predstavljaju, redom, broj gradova, broj telefonskih linija i redne brojeve gradova NishB i ABNish (n ≤ 10⁴, m ≤ 10⁵). Gradovi su numerisani brojevima od 1 do n. U narednih m redova nalaze se po tri prirodna broja a_i, b_i i t_i koji označavaju da postoji linija od grada a_i do grada b_i i da je potrebno t_i mikrosekundi za uspostavljanje veze (a_i ≠ b_i, t_i ≤ 10⁵). Između dva grada mogu postojati više telefonskih linija.

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom reduizlazne datoteke ispisati najveći broj telefonskih linija koje je moguće srušiti.

Primer 1.

4 6 1 2
1 2 1
2 1 5
2 4 1
1 4 2
1 3 3
4 3 2
2 1 4

2

Objašnjenje.

Rušenjem druge i četvrte telefonske linije, minimalna rastojanja od centara do ostalih gradova ostaju ista, dok je to nemoguće ako srušimo tri ili više linija.

Napomena.

U 50% test primera biće n ≤ 10³.