#include<bits/stdc++.h>
// no of bits to store no 2e5 is 19
// 2e5 ka 5 times square root lene se 2 or 3 ke pass pahunch jate hai
using namespace std;

#define int               long long
#define mod               1000000007
#define MOD               1000000007
#define MAX               1000000000
#define inf               1e18
#define ff                first
#define ss                second
#define mp                make_pair
#define pb                push_back
#define pii               pair<int,int>
#define mii               map<int, int>
#define all(x)            (x).begin(), (x).end()
#define fill(a,b)         memset(a, b, sizeof(a))
#define sp(x,y)           fixed<<setprecision(y)<<x
#define setbits(x)        __builtin_popcount(x)
#define fast_in_out       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define ll                long long

//   powermod(a,b,m) ==  powermod(a,b%(m-1),m)  when m is prime fermat's theorem a^(p-1) %p=1 p is prime
int powermod(int a,int b,int c) //  gives (a^b)%c
{
    int ans = 1,tempans=a%c;
    while(b>0)
    {
        if(b&1==1)
        {
            ans=(ans*tempans)%c;
        }
             tempans=(tempans*tempans)%c;
             b=b>>1;
    }
    return ans;
}

int modinverse(int a,int m)   // gives a inverse wrt m and m is prime
{
    return powermod(a,m-2,m);
}

ll add(ll x, ll y) {
   x += y;
   if (x >= mod) return x - mod;
   return x;
}
ll sub(ll x, ll y) {
   x -= y;
   if (x < 0) return x + mod;
   return x;
}
ll mult(ll x, ll y) {
   return (x * y) % mod;
}
// my template                                              m
// prime factorization                                      pf
// ncr and factorials                                       ncr
// matrix exponentiation of fibonacci series in log(n)      matexpofib
// cycles in a graph                                        cycle
// prime factorization in log(n)                            spf


vector<pair<int,pii>> edges[100005];// city
void solve()
{
  int n,m,st,en;
  cin>>n>>m>>st>>en;
  while(m--)
  {
     int x,y,ti,ki;
     cin>>x>>y>>ti>>ki;
     edges[x].pb({y,{ti,ki}});
      edges[y].pb({x,{ti,ki}});

  }

  // dis ind
  priority_queue<pii> q;
  vector<int> dis(n+1,inf);
  vector<bool > vis(n+1,false);

  dis[st]=0;
  q.push({0,st});
  while(!q.empty())
  {
     pii p= q.top();
     q.pop();
     if(vis[p.ss])
      continue;
     vis[p.ss]=true;
    // cout<<p.ss<<endl;

     for(auto ch: edges[p.ss])
     {
       // cout<<"and " <<ch.ff<<" "<<ch.ss.ff<<" "<<ch.ss.ss<<endl;
        int k= ch.ss.ss;
        int z= dis[p.ss]%k;
       // cout<<dis[p.ss]<<" "<<k<<" "<<z<<endl;
        if(z!=0)
        {
           z= k-z;
        }
        z+=(dis[p.ss]+ch.ss.ff);

        if(!vis[ch.ff]&&z<dis[ch.ff])
        {
           dis[ch.ff]=z;
           q.push({-z,ch.ff});

        }

     }
  }
  if(dis[en]==inf)
   dis[en]=-1;
  cout<<dis[en]<<endl;





}


int32_t main()
{
  fast_in_out;

  int t=1;//cin>>t;
  int count=0;


   while(t--)
   {
       count++;
       solve();
   }
}

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rrep(i, n) for(ll i = n - 1; i > -1; i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
template <class X> void print(X x) { cout << x << endl; }
#define in(A, n)                                                                                                       \
    rep(i, n) {                                                                                                        \
        cin >> f;                                                                                                      \
        A.push_back(f);                                                                                                \
    }

void print(vl x) {
    for(ll i : x) {
        cout << i << " ";
    }
    cout << endl;
}
const ll INF = (1LL << 61) - 1;
const ll MOD = 1000000007 /*998244353*/;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, h, x, y, z, p, q, n, t, r, k, w, l, ans, i, j, u, v, m;
ll codeforces = 1;
string S, T;
vector<vl> g(MAX_N);
vector<vl> A;
vl C, D;
ll co[1 << 17][17];
void input() {
    cin >> n;
    rep(i, n) {
        cin >> x >> y >> z;
        A.pb({x, y, z});
    }
}
void solve() {
    rep(i, 1 << n) {
        if(i) {
            rep(j, n) { co[i][j] = INF; }
        }
    }
    co[1][0] = 0;
    k = 1 << n;
    rep(i, k) {
        C.clear();
        D.clear();
        rep(j, n) {
            if(i & (1 << j)) {
                C.pb(j);
            } else {
                D.pb(j);
            }
        }
        for(ll x : C) {
            for(ll y : D) {
                co[i + (1 << y)][y] =
                    min(co[i + (1 << y)][y],
                        co[i][x] + abs(A[x][0] - A[y][0]) + abs(A[x][1] - A[y][1]) + max(0ll, A[y][2] - A[x][2]));
            }
        }
    }

    ans = INF;
    rep(i, n) {
        if(i)
            ans =
                min(ans, co[k - 1][i] + abs(A[0][0] - A[i][0]) + abs(A[0][1] - A[i][1]) + max(0ll, A[0][2] - A[i][2]));
    }

    print(ans);
}
int main() {
    // cout<<fixed<<setprecision(15);
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    while(codeforces--) {
        solve();
    }
}