roads.cpp

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

#define ar array

const int N = 105;
const int K = 10005;
const int INF = 0x3f3f3f3f;

struct road {
  int v, w, c;
  road() { v = w = c = 0; }
  road(int v, int w, int c): v(v), w(w), c(c) {}
  bool operator()(road a, road b) {
    if (a.c == b.c) return a.w > b.w;
    return a.c > b.c;
  }
};

int n, m, k;
vector<road> adj[N];
int dist[N], cost[N];

void solve() {
  cin >> k >> n >> m;
  for (int i = 1; i <= n; i++) {
    adj[i].clear();
  }
  for (int i = 0; i < m; i++) {
    int u, v, w, c;
    cin >> u >> v >> w >> c;
    adj[u].push_back(road(v, w, c));
  }
  memset(cost, 0x00, sizeof(cost));
  memset(dist, 0x3f, sizeof(dist));
  priority_queue<road, vector<road>, road> pq;
  pq.push({1, 0, 0});
  while (pq.size()) {
    auto i = pq.top(); pq.pop();
    int v = i.v, w = i.w, c = i.c;
    if (w >= dist[v] || c > k) continue;
    dist[v] = w;
    cost[v] = c;
    for (auto &j : adj[i.v]) {
      pq.push(road(j.v, i.w + j.w, i.c + j.c));
    }
  }
  if (dist[n] == INF) dist[n] = -1;
  cout << dist[n] << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T; cin >> T;
  while (T--) solve();
}