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 iz datoteke nishtel.in.) 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.

(Izlazne podatke upisati u datoteku nishtel.out) U prvom i jedinom redu izlazne 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³.

#include <stdlib.h>
#include <stdio.h>
#include <vector>

using namespace std;

const int inf = 2000000000;
const int MaxN = 10010;
const int MaxM = 100010;

struct edge {
  int v, w;
  edge(int _v, int _w) {
    v = _v; w = _w;
  }
};

int n, m, A, B, u, v, w, sol;
int dA[MaxN], dB[MaxN], d[MaxN];
int adj[MaxM], weight[MaxM], a[MaxM], b[MaxM], w1[MaxM];
int p[MaxN], deg[MaxN];
bool mark[MaxN];

struct Heap {
  int heap_size;
  int h[MaxN];
  int posInHeap[MaxN];

  void init(int n) { 
    heap_size = n; 
    for (int i = 1; i <= n; i++) {
      h[i] = i;
      posInHeap[i] = i;
    }
  }

  bool empty() { return (heap_size == 0); }

  void update(int u, int newVal) {
    int f, s;
    d[u] = newVal;
    s = posInHeap[u]; 
    f = s / 2;

    while (f != 0 && d[ h[f] ] > d[u]) {
      h[s] = h[f];
      posInHeap[ h[f] ] = s;
      s = f; f = s / 2;
    }
    h[s] = u;
    posInHeap[u] = s;
  }

  int extractMin() {
    int f, s, u, min;
    min = h[1];
    h[1] = u = h[heap_size--];
    f = 1;
    s = 2 * f;
    if (heap_size > s && d[ h[s + 1] ] < d[ h[s] ]) s++;

    while (s <= heap_size && d[u] > d[ h[s] ]) {
      h[f] = h[s];
      posInHeap[ h[s] ] = f;
      f = s; s = 2 * f;
      if (heap_size > s && d[ h[s + 1] ] < d[ h[s] ]) s++;
    }
    h[f] = u;
    posInHeap[u] = f;

    return min;
  }    
};

Heap H;

void Dijkstra(int START) {
  int u, v, w, min;
  for (int i = 1; i <= n; i++) d[i] = inf;
  H.init(n);
  H.update(START, 0);

  while (!H.empty()) {
    u = H.extractMin();
    for (int i = p[u]; i < p[u] + deg[u]; i++) {
      v = adj[i];
      w = weight[i];
      if (d[u] + w < d[v])
        H.update(v, d[u] + w);
    }
  }
}

int main() {

  FILE* inFile = fopen("nishtel.in", "r");
  FILE* outFile = fopen("nishtel.out", "w");

  for (int i = 1; i <= n; i++) deg[i] = 0;
  fscanf(inFile, "%d%d%d%d", &n, &m, &A, &B);
  for (int i = 1; i <= m; i++) {
    fscanf(inFile, "%d%d%d", &a[i], &b[i], &w1[i]);
    deg[a[i]]++;
  }

  p[0] = 0;
  for (int i = 1; i <= n; i++) 
    p[i] = p[i - 1] + deg[i - 1];

  for (int i = 1; i <= m; i++) { 
    adj[p[a[i]]] = b[i];
    weight[p[a[i]]] = w1[i];
        p[a[i]] = p[a[i]] + 1;
  }
    for (int i = 1; i <= n; i++)
    p[i] = p[i - 1] + deg[i - 1];
  
  Dijkstra(A);
  for (int i = 1; i <= n; i++) dA[i] = d[i];
  Dijkstra(B);
  for (int i = 1; i <= n; i++) dB[i] = d[i];

  sol = m - 2 * n + 2;
  for (int i = 1; i <= n; i++) mark[i] = false;

  for (u = 1; u <= n; u++)
    for (int i = p[u]; i < p[u] + deg[u]; i++) {
      v = adj[i];
      w = weight[i];
      if (!mark[v] && dA[v] - dA[u] == w && dB[v] - dB[u] == w) {
        mark[v] = true;
        sol++;
      }
    }
  fprintf(outFile, "%d\n", sol);

  fclose(inFile);
  fclose(outFile);
  return 0;
}

const
   MaxN = 10010;
   MaxM = 100010;
   inf = 2000000000;


var
   inFile, outFile : Text;
   n, m, A, B, u, v, w, sol, i, heap_size : longint;
   a1, b1, w1, adj, weight : array[0..MaxM] of longint;
   d, dA, dB, p, deg : array[0..MaxN] of longint;
   h, posInHeap : array[0..MaxN] of longint;
   mark : array[0..MaxN] of boolean;


procedure Input;
var
   i, u, v, w: longint;

begin

   assign( inFile, 'nishtel.in' );
   reset( inFile );
   fillchar( deg, sizeof( deg ), 0 );

   readln( inFile, n, m, A, B );
   for i := 1 to m do begin
      readln( inFile, u, v, w );
      deg[ u ] := deg[ u ] + 1;
      a1[ i ] := u; b1[ i ] := v; w1[ i ] := w;
   end;

   close( inFile );

end;


procedure Output;
begin

   assign( outFile, 'nishtel.out');
   rewrite( outFile );
   writeln( outFile, sol);
   close( OutFile );

end;


(* simulacija liste preko counting sorta *)
procedure ListSimulation;
var
   i: longint;

begin

   p[0] := 0;
   for i := 1 to n do
      p[ i ] := p[ i - 1 ] + deg[ i - 1 ];

   for i := 1 to m do begin
      adj[ p[ a1[ i ] ] ] := b1[ i ];
      weight[ p[ a1[ i ] ] ] := w1[ i ];
      p[ a1[ i ] ] := p[ a1[ i ] ] + 1;
   end;

   for i := 1 to n do
      p[ i ] := p[ i - 1 ] + deg[ i - 1 ];

end;


procedure updateHeap( u, newVal : longint );
var
   f, s : longint;

begin

   d[ u ] := newVal;
   s := posInHeap[ u ];
   f := s div 2;

   while ((f <> 0) and (d[ h[ f ] ] > d[ u ])) do begin
      h[ s ] := h[ f ];
      posInHeap[ h[ f ] ] := s;
      s := f; f := s div 2;
   end;

   h[ s ] := u;
   posInHeap[ u ] := s;

end;


function extractMin: longint;
var
   f, s, u, min : longint;

begin

   min := h[ 1 ];
   u := h[ heap_size ];
   h[ 1 ] := u;
   heap_size := heap_size - 1;
   f := 1;
   s := 2 * f;
   if ((heap_size > s) and (d[ h[ s + 1 ] ] < d[ h[ s ] ])) then
      s := s + 1;

   while ((s <= heap_size) and (d[ u ] > d[ h[ s ] ])) do begin
      h[ f ] := h[ s ];
      posInHeap[ h[ s ] ] := f;
      f := s; s := 2 * f;
      if ((heap_size > s) and (d[ h[ s + 1 ] ] < d[ h[ s ] ])) then
         s := s + 1;
   end;

   h[ f ] := u;
   posInHeap[ u ] := f;
   extractMin := min;

end;


procedure Dijkstra( START : longint );
var
  u, v, w : longint;

begin

   for i := 1 to n do begin
      d[ i ] := inf;
      h[ i ] := i;
      posInHeap[ i ] := i;
   end;
   heap_size := n;
   updateHeap( START, 0 );

   while (heap_size > 0) do begin
      u := extractMin;
      for i := p[ u ] to p[ u ] + deg[ u ] - 1 do begin
         v := adj[ i ]; w := weight[ i ];
         if (d[ u ] + w < d[ v ]) then
            updateHeap( v, d[ u ] + w );
      end;
   end;

end;


begin

   Input;
   ListSimulation;

   Dijkstra( A );
   for i := 1 to n do dA[ i ] := d[ i ];
   Dijkstra( B );
   for i := 1 to n do dB[ i ] := d[ i ];

   sol := m - 2 * n + 2;
   for i := 1 to n do mark[ i ] := false;

   for u := 1 to n do
      for i := p[ u ] to p[ u ] + deg[ u ] - 1 do begin
         v := adj[ i ]; w := weight[ i ];
         if ((not mark[ v ]) and (dA[ v ] - dA[ u ] = w) and (dB[ v ] - dB[ u ] = w))
         then begin
            mark[ v ] := true;
            sol := sol + 1;
         end;
      end;

   Output;

end.