#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1000000007;
ll INF = 1001001001;

ll max(int a, ll b)
{
    if (a < b)
    {
        return b;
    }
    else
    {
        return a;
    }
}

ll min(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    ll N;
    cin >> N;
    vector<vector<ll>> xyz(N, vector<ll>(3));
    rep(i, N)
    {
        cin >> xyz[i][0] >> xyz[i][1] >> xyz[i][2];
    }

    vector<vector<ll>> dist(N, vector<ll>(N));
    rep(i, N) rep(j, N)
    {
        dist[i][j] = abs(xyz[j][0] - xyz[i][0]) + abs(xyz[j][1] - xyz[i][1]) + max(0, xyz[j][2] - xyz[i][2]);
    }

    vector<ll> pow2(N + 1, 1);
    for (int i = 1; i < N + 1; i++)
    {
        pow2[i] = pow2[i - 1] * 2;
    }

    vector<vector<ll>> dp(pow2[N], vector<ll>(N, INF));
    rep(i, N)
    {
        dp[1 << i][i] = dist[i][0];
    }

    rep(i, pow2[N]) rep(j, N)
    {
        if ((i >> j & 1) != 1)
            continue;
        rep(k, N)
        {
            if ((i >> k & 1) == 1)
                continue;
            dp[i | (1 << k)][k] = min(dp[i | 1 << k][k], dp[i][j] + dist[k][j]);
        }
    }
    cout << dp[pow2[N] - 1][0] << endl;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)

// #define LOCAL 1;
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

template<typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
  out << "[";
  size_t last = v.size() - 1;
  for (size_t i = 0; i < v.size(); ++i) {
    out << v[i];
    if (i != last)
      out << ", ";
  }
  out << "]";
  return out;
}

template<typename F, typename S>
ostream& operator<< (ostream& out, const pair<F,S>& p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}

template< typename T >
struct edge {
  int src, to;
  T cost, kbai;
  

  edge(int to, T cost, T kbai) : src(-1), to(to), cost(cost), kbai(kbai) {}

  edge(int src, int to, T cost, T kbai) : src(src), to(to), cost(cost), kbai(kbai) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;
int n,m,x,y;
template< typename T >
vector< T > dijkstra(WeightedGraph< T > &g, int s) {
  const auto INF = numeric_limits< T >::max();
  // vector< T > dist_kbai(g.size(), INF);
  vector< T > dist(g.size(), INF);

  using Pi = pair< T, int >;
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  dist[s] = 0;
  // dist_kbai[s] = 0;
  que.emplace(dist[s], s);
  while(!que.empty()) {
    T cost;
    int idx;
    tie(cost, idx) = que.top();
    que.pop();
    // dbg(idx);
    // dbg(cost);
    if(dist[idx] < cost) continue;
    for(auto &e : g[idx]) {
      T tcost = cost;
      tcost += (e.kbai - tcost%e.kbai)%e.kbai;
      auto next_cost = tcost + e.cost;
      if(dist[e.to] <= next_cost) continue;
      dist[e.to] = next_cost;
  
 
      que.emplace(dist[e.to], e.to);
    }
  }
  return dist;
}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> m >> x >> y;
  --x;--y;
  WeightedGraph< ll > g(n);
  rep(i,m) {
    ll a, b, t, k;
    cin >> a >> b >> t >> k;
    --a;--b;
    g[a].emplace_back(b, t, k);
    g[b].emplace_back(a, t, k);
  }
  auto dist  = dijkstra(g, x);

  if(dist[y]==numeric_limits<ll>::max()) cout << -1 << endl;
  else cout << dist[y] << endl;
  
  return 0;
    

}
