设计 DP 状态 $f_{sum,u}$ 表示目前到达 $u$ 节点且 $\sum a_i = sum$ 时，$\sum b_i$ 的最小值。 注意到 $a_i \gt 0$，$sum$ 相同的状态之间没有转移。 所以可以直接枚举 $sum$ 再枚举可行的边，直接转移。 时间复杂度 $O(NM\max\{a_i\})$。

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

const int INF = INT_MAX;

int main() {
    vector<vector<vector<int>>> graph;
    int N, M;
    cin >> N >> M;
    graph.resize(N + 1);

    int max_a_sum = 0;
    for (int i = 0; i < M; ++i) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        graph[u].push_back({v, a, b});
        max_a_sum += a;
    }

    vector<vector<int>> dp(max_a_sum + 1, vector<int>(N + 1, INF));
    dp[0][1] = 0;

    for (int sum = 0; sum <= max_a_sum; ++sum) {
        for (int u = 1; u <= N; ++u) {
            if (dp[sum][u] == INF) continue;
            for (auto& edge : graph[u]) {
                int v = edge[0];
                int a = edge[1];
                int b = edge[2];
                int new_sum = sum + a;
                if (new_sum > max_a_sum) continue;
                if (dp[new_sum][v] > dp[sum][u] + b) {
                    dp[new_sum][v] = dp[sum][u] + b;
                }
            }
        }
    }

    int min_product = INF;
    int best_sum_a = 0, best_sum_b = 0;
    for (int sum_a = 0; sum_a <= max_a_sum; ++sum_a) {
        if (dp[sum_a][N] != INF) {
            int sum_b = dp[sum_a][N];
            int product = sum_a * sum_b;
            if (product < min_product || (product == min_product && sum_a < best_sum_a)) {
                min_product = product;
                best_sum_a = sum_a;
                best_sum_b = sum_b;
            }
        }
    }

    cout << best_sum_a << " " << best_sum_b << endl;

    return 0;
}