Floyd

/*
█████████████.....██████....██.........█....██████████....██.........██.
██.........██.......██......█.█........█....██......██.....██.......██..
██.........██.......██......█..█.......█....██......██......██.....██...
██.........██.......██......█...█......█....██......██.......██...██....
██.........██.......██......█....█.....█....██......██........██.██.....
██.........██.......██......█.....█....█....██......██.........███......
█████████████.......██......█.....█....█....██████████.........███......
██..................██......█......█...█....██......██.........███......
██..................██......█......█...█....██......██.........███......
██..................██......█.......█..█....██......██.........███......
██..................██......█.......█..█....██......██.........███......
██..................██......█........█.█....██......██.........███......
██..................██......█........█.█....██......██.........███......
██................██████....█.........██....██......██.........███......
*/
#include <bits/stdc++.h>
// #define DEBUG
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FF first
#define SS second
#define watch(x) cerr << (#x) << " is " << x << endl

ld P[101][101];

const ll INF = 1ll<<40;

int main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
    #ifdef DEBUG
    #else
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int n, m;
    cin >> n >> m;
    ld temp;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> temp;
            if(temp != -1001) {
                P[i][j] = temp;
            }
            else {
                P[i][j] = INF;
            }
            // cout << P[i][j] << " ";
        }
        // cout << endl;
    }
    // for(int i = 0; i < n; i++) {
    //  for(int j = 0; j < n; j++) {
    //      cout << P[i][j] << " ";
    //  }
    //  cout << endl;
    // }
    // cout << "\n\n\n";
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    // cout << P[i][j] << "\n";
                    // cout << P[i][k] + P[k][j] << "\n";
                    P[i][j] = min( P[i][j] , P[i][k] + P[k][j] );
                }
        }
    }
    // for(int i = 0; i < n; i++) {
    //  for(int j = 0; j < n; j++) {
    //      cout << P[i][j] << " ";
    //  }
    //  cout << endl;
    // }
    int l, r;
    for(int i = 0; i < m; i++) {
        cin >> l >> r;
        l--;
        r--;
        if(P[l][r] != INF) {
            cout << P[l][r] << "\n";
        }
        else {
            cout << "No path\n";
        }
    }
    return 0;
}