#include <bits/stdc++.h>

using namespace std;
// Constants and macros
#define INF 		(int)1e9
#define EPS 		1e-9
#define bitcount 	__builtin_popcount
#define gcd 		__gcd
#define forall(i,a,b) 	for(int i=a;i<b;i++)
#define pb 		push_back
#define mp		make_pair
#define MAX(a,b)	( (a)>(b) ? (a):(b))
#define MIN(a,b)	( (a)<(b) ? (a):(b))
#define s(a)		scanf("%d", &a)
#define ss(a,b)		scanf("%d %d", &a,&b)
#define sss(a,b,c)	scanf("%d %d %d", &a,&b,&c)
#define sl(a)		scanf("%I64d", &a)

int  K, N, M;
long long totc;
struct edge{
	int node;
	int time;
	int cost;
};


vector<edge> 	adj[10005];
bool 		vis[10005];
int		dis [10005]; // dis to i;
int		mc [10005]; // mincost to i;

bool d(int fr, int to){
	totc = 0;
	if (fr == to) return true;
	for (int i = 0; i < N+1;i++){
		dis[i] = INF;
		mc[i]  = INF;
	}
	priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>> > pq; // cost, time, node;
	pq.push(mp(0,mp(0,fr)));
	while (!pq.empty()){
		pair<int,pair<int,int>> cur = pq.top();
		int cc = cur.first, ct = cur.second.first, cn = cur.second.second;
		//cout << cc << " " << ct << " " << cn << " ";
		pq.pop();
		//if (vis[cn] == true) continue;
		if (ct < dis[cn]){
		//	cout << "added";
			dis[cn] = ct;
			mc [cn] = cc;
			for (auto k: adj[cn]){
				int kc = k.cost, kt = k.time, kn = k.node;
				if (kc+cc < K ){
		//			cout <<endl << kc << " " << kt << " " << kn;
					pq.push(mp(kc+cc,mp(kt+ct,kn)));
				}
			}
			vis[cn] = true;
		}
		//cout << endl;
	}
	totc = dis[to];
	if (totc==INF)
		return false;
	else
		return true;
}

int a, b, t, h;
int main(){
	sss(K,N,M);
	forall(i,0,M){
		ss(a,b);
		ss(t,h);
		adj[a].pb({b,t,h});
		adj[b].pb({a,t,h});
	}
	ss(a,b);
	if (d(a,b)){
		printf("%lld",totc);
	}
	else {
		printf("-1");
	}
}