#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

const int DEBUG=0;

//http://tubo28.me/algorithm/dinic/
using Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(int s, int d, Flow w) : src(s), dst(d), cap(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
  g[a].push_back(Edge(a, b, w));
  g[b].push_back(Edge(b, a, w));
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].push_back(Edge(a, b, w)); }
struct dinic {
    int n, s, t;
    std::vector<int> level, prog, que;
    std::vector<std::vector<Flow> > cap, flow;
    std::vector<std::vector<int> > g;
    Flow inf;
    dinic(const Graph &graph)
        : n(graph.size()),
          cap(n, std::vector<Flow>(n)),
          flow(n, std::vector<Flow>(n)),
          g(n, std::vector<int>()),
          inf(std::numeric_limits<Flow>::max() / 8) {
        for (int i = 0; i < n; i++) {
            for (auto &e : graph[i]) {
                int u = e.src, v = e.dst;
                Flow c = e.cap;
                cap[u][v] += c;
                cap[v][u] += c;
                flow[v][u] += c;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
    }
    inline Flow residue(int u, int v) { return cap[u][v] - flow[u][v]; }
    Flow solve(int s_, int t_) {
        this->t = t_, this->s = s_;
        que.resize(n + 1);
        Flow res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, inf);
        }
        return res;
    }
    bool levelize() {
        int l = 0, r = 0;
        level.assign(n, -1);
        level[s] = 0;
        que[r++] = s;
        while (l != r) {
            int v = que[l++];
            if (v == t) break;
            for (const int &d : g[v])
                if (level[d] == -1 && residue(v, d) != 0) {
                    level[d] = level[v] + 1;
                    que[r++] = d;
                }
        }
        return level[t] != -1;
    }
    Flow augment(int v, Flow lim) {
        Flow res = 0;
        if (v == t) return lim;
        for (int &i = prog[v]; i < (int)g[v].size(); i++) {
            const int &d = g[v][i];
            if (residue(v, d) == 0 || level[v] >= level[d]) continue;
            const Flow aug = augment(d, std::min(lim, residue(v, d)));
            flow[v][d] += aug;
            flow[d][v] -= aug;
            res += aug;
            lim -= aug;
            if (lim == 0) break;
        }
        return res;
    }
};

// http://kirika-comp.hatenablog.com/entry/2018/01/29/020648

typedef long long int lint;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
typedef pair<lint, lint> pll;
typedef pair<pii,lint>ppiil;

const int N = 100100;
int n;
vector<ppiil> edges[N];

pll add(pll a, pll b) {
  if (a.first != b.first) return min(a,b);
  return pll(a.first,a.second+b.second);
}
pll mul(pll a,pll b){
  return pll(a.first+b.first,min(a.second,b.second));
}

const lint inf=1e14;

/*
 * edges に辺の情報(終点、距離)を入れると、(sからの最短距離,最短距離の道の本数%mod)を保持する vector を返す。
 */
vector<pll> calc(int s) {
  vector<pll> dp(n, pll(inf, 0));
  vector<bool> vis(n, false);
  priority_queue<pli, vector<pli> , greater<pli> > que;
  dp[s] = pll(0, inf);
  que.push(pli(0, s));
  while (not que.empty()) {
    pli vd = que.top(); que.pop();
    int v = vd.second;
    if (vis[v]) continue;
    vis[v] = true;
    rep(i, edges[v].size()) {
      ppiil wc = edges[v][i];
      pii wd=wc.first;
      int w=wd.first;
      int d=wd.second;
      lint c = wc.second;
      if(DEBUG){
	cerr<<v << "==>" << w<<" "<<d<<" "<<c<<endl;
      }
      dp[w]=add(dp[w],mul(dp[v],pll(d,c)));
      que.push(pli(dp[w].first,w));
    }
  }
  return dp;
}

int main(){
  int m,s,t;
  cin>>n>>m>>s>>t;
  s--,t--;
  vi uu(m),vv(m),dd(m),cc(m);
  rep(i,m){
    int u,v,d,c;
    cin>>u>>v>>d>>c;
    u--,v--;
    edges[u].push_back(ppiil(pii(v,d),c));
    uu[i]=u;
    vv[i]=v;
    dd[i]=d;
    cc[i]=c;
  }
  vector<pll> dp=calc(s);
  rep(i,N)
    edges[i].clear();
  rep(i,m){
    edges[vv[i]].push_back(ppiil(pii(uu[i],dd[i]),cc[i]));
  }
  vector<pll>dp2=calc(t);
  Graph g(n);
  rep(i,m){
    if(dp[uu[i]].first+dp2[vv[i]].first+dd[i]==dp[t].first){
      add_arc(g,uu[i],vv[i],cc[i]);
    }
  }
  dinic dn(g);
  cout<<dn.solve(s,t)<<endl;
  if(DEBUG){
    rep(i,n){
      cerr<<"dp["<<i<<"]:"<<dp[i].first<<" "<<dp[i].second<<endl;
    }
  }
}



Measured memory_bytes: 5640