Consider an air travel network of $n$ cities where passengers have two booking options for any city pair $(i, j)$: a standard economy ticket with price $Y_{i,j}$ or a special transfer-discounted ticket priced at $T_{i,j}$. The discounted fare is only applicable when the ticket is used as part of a two-segment journey with an intermediate stop. Given $q$ queries, each specifying a departure city $u$ and arrival city $v$, the objective is to compute the minimum travel cost for each trip. A valid itinerary consists of either a direct flight $u \to v$ or a connection via a single hub city $w$ (combining $u \to w$ and $w \to v$). Unavailable routes are marked with $-1$.

With $n \leq 100$, an exhaustive search per query provides adequate performence. For each origin-destinatino pair $(u, v)$:

Initialize the optimal cost to a sufficiently large sentinel value (e.g., $4 \times 10^{18}$). First, verify if a direct economy flight is offered; if $Y_{u,v} \neq -1$, set the current best to $Y_{u,v}$. Subsequently, enumerate every possible intermediate city $w \in [1, n]$. If both connecting segments via $w$ are available (i.e., $T_{u,w} \neq -1$ and $T_{w,v} \neq -1$), calculate the combined fare $T_{u,w} + T_{w,v}$ and retain the lesser value between this sum and the current optimum.

After evaluating all candidate, if the optimal cost remains unchanged from its initial sentinel value, output $-1$ indicating no feasible route exists; otherwise, output the computed minimum. This approach executes in $O(n)$ time per query, yielding an overall complexity of $O(q \cdot n)$.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int numCities, numQueries;
    cin >> numCities >> numQueries;
    
    vector<vector<long long>> directFare(numCities + 1, vector<long long>(numCities + 1));
    vector<vector<long long>> transitFare(numCities + 1, vector<long long>(numCities + 1));
    
    for (int i = 1; i <= numCities; ++i) {
        for (int j = 1; j <= numCities; ++j) {
            cin >> directFare[i][j];
        }
    }
    
    for (int i = 1; i <= numCities; ++i) {
        for (int j = 1; j <= numCities; ++j) {
            cin >> transitFare[i][j];
        }
    }
    
    while (numQueries--) {
        int source, destination;
        cin >> source >> destination;
        
        const long long INF = 4e18;
        long long bestCost = INF;
        
        if (directFare[source][destination] != -1) {
            bestCost = directFare[source][destination];
        }
        
        for (int hub = 1; hub <= numCities; ++hub) {
            if (transitFare[source][hub] != -1 && transitFare[hub][destination] != -1) {
                long long totalTransit = transitFare[source][hub] + transitFare[hub][destination];
                if (totalTransit < bestCost) {
                    bestCost = totalTransit;
                }
            }
        }
        
        if (bestCost == INF) {
            bestCost = -1;
        }
        cout << bestCost << '\n';
    }
    
    return 0;
}