#include <bits/stdtr1c++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

struct s {
  ll t, i, h;
  s(ll tt, ll ii, ll hh) : t(tt), i(ii), h(hh) {}
  bool operator<(const s& b) const {
    return t > b.t;
  }
};

struct p {
  int b, t, h;
  p(ll bb, ll tt, ll hh) : b(bb), t(tt), h(hh) {}
};

vector<p> adj[2005];
ll mt[2005][201];
bool vis[2005][201];

int main() {
  ios::sync_with_stdio(0);
  int k, n, m; cin >> k >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, t, h;
    cin >> a >> b >> t >> h;
    adj[a].push_back(p(b,t,h));
    adj[b].push_back(p(a,t,h));
  }
  for (int i = 0; i < 2005; i++)
    for (int j = 0; j < 201; j++)
      mt[i][j] = 0x3f3f3f3f;
  int A, B; cin >> A >> B;
  priority_queue<s> pq;
  pq.push(s(0,A,k));
  mt[A][k] = 0;
  while (pq.size()) {
    s t = pq.top();
    pq.pop();
    if (t.i == B) {
      cout << t.t << "\n";
      goto VELOCIRAPTOR;
    }
    for (int i = 0; i < adj[t.i].size(); i++) {
      ll nh = t.h-adj[t.i][i].h;
      if (nh <= 0)
        continue;
      ll nt = t.t+adj[t.i][i].t;
      int b = adj[t.i][i].b;
      if (vis[b][nh])
        continue;
      mt[b][nh] = min(mt[b][nh],nt);
      pq.push(s(nt,b,nh));
    }
    vis[t.i][t.h] = true;
  }
  cout << "-1\n";
  VELOCIRAPTOR:
  return 0;
}