1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;

vector<pair<ii, int>> G[101];
ll dist[101][10001];

int main() {
	int B, M, N; cin >> B >> M >> N;
	while (M--) {
		int a, b, t, c; cin >> a >> b >> t >> c;
		G[a].emplace_back(ii(t, c), b), G[b].emplace_back(ii(t, c), a);
	}
	memset(dist, '?', sizeof dist);
	dist[0][0] = 0;
	priority_queue<pair<ll, ii>, vector<pair<ll, ii>>, greater<pair<ll, ii>>> pq;
	pq.emplace(0, ii(0, 0));
	while (!pq.empty()) {
		ll d = pq.top().f; ii u = pq.top().s;
		pq.pop();
		if (d > dist[u.f][u.s]) continue;
		for (auto& v : G[u.f]) {
			if (u.s + v.f.f < 1e4 && d + v.f.s < dist[v.s][u.s + v.f.f]) {
				dist[v.s][u.s + v.f.f] = d + v.f.s;
				pq.emplace(dist[v.s][u.s + v.f.f], ii(v.s, u.s + v.f.f));
			}
		}
	}
	int ans = 0;
	while (ans < 1e4 && dist[1][ans] > B) ++ans;
	cout << (ans < 1e4 ? ans : -1) << '\n';
}