#include <bits/stdc++.h>
using namespace std;
#define END '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define bug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define loop(i, a, b) for(int i = (a); i < (b); i++)
#define loopb(i, b, a) for(int i = (b); i > (a); --i) 
const int inf = 1e18;  
const int mod = 1e9+7;
const int mod1 = 998244353;
const int nax = 200005;
struct road
 {
  int v, t, k;
 };
int n, m, a, b, x, y, t, k;
vector<road> adj[nax];
int dp[nax];
void calc()
 {
  priority_queue<pii> q;
  q.push({0, x});
  while(!q.empty())
   {
    int time = -q.top().ff;
    int node = q.top().ss;
    q.pop();
    for(auto x : adj[node])
       {
        int div = (time + x.k - 1)/x.k;
        int tot = div*x.k + x.t;
        if(dp[x.v] > tot)
           {
            dp[x.v] = tot;
            q.push({-dp[x.v], x.v});
           }
       }
   } 
 }
void solve()
 {
  cin>>n>>m>>x>>y;
  for(int i = 1; i <= n; i++)
     dp[i] = inf;
  dp[x] = 0;
  for(int i = 1; i <= m; i++)
     {
      cin>>a>>b>>t>>k;
      road A;
      A.v = b;
      A.t = t;
      A.k = k;
      adj[a].pb(A);
      A.v = a;
      adj[b].pb(A);
     }
  calc();
  if(dp[y] == inf)
     dp[y] = -1;
  cout<<dp[y];
 } 
int32_t main()
 {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
   int t = 1;
   //cin>>t;
   while(t--)
     solve();
 // cerr<<END<<1.0*clock()/CLOCKS_PER_SEC;
  return 0;
} 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
const ll mod = 10e8 + 7;
const ll inf = (1LL << 60);

vector<ll> x(20), y(20), z(20);

ll c(int i, int j) {
    return abs(x[i] - x[j]) + abs(y[i] - y[j]) + max(0LL,z[j] - z[i]);
}

int main(){
    int n; cin >> n;
    rep(i,n) cin >> x[i] >> y[i] >> z[i];
    vector<vector<pair<ll,int>>> dp((1<<n),vector<pair<ll,int>>(n,make_pair(inf,-1)));
    rep(i,n) dp[(1<<i)][i] = make_pair(c(i,0),i);
    rep(i,(1<<n)){
        bitset<20> s(i);
        rep(j,n){
            if(s.test(j)) continue;
            rep(k,n){
                if(!s.test(k)) continue;
                ll x, y, z, w;
                tie(x,y) = dp[i|(1<<j)][j];
                tie(z,w) = dp[i][k];
                if(x > z + c(j,k)){
                    dp[i|(1<<j)][j] = make_pair(z + c(j,k),w);
                }
            }
        }
    }
    cout << dp[(1<<n)-1][0].first << endl;
}