#include <iostream>
#include <stdio.h>

using namespace std;

int n, m, a, b;

int main () {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);

        cin >> n>> m;
        int d[n][n];
        int c[m][2];

        for(int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                        cin >> d[i][j];
                }
        }

        for (int i=0; i<m; i++) {
                for (int j=0; j<2; j++) {
                        cin >> c[i][j];
                }
        }

        for (int i=0; i<n; i++) {
                for (int j=0; j<=n; j++) {
                        if (d[i][j]==(-1001)) {
                                d[i][j]=10000;
                        }
                }
        }

        for (int k=0; k<n; k++) {
                for (int i=0; i<n; i++) {
                        for(int j=0; j<n; j++) {
                                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
                        }
                }
        }

        for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                        if (d[i][j]==10000) {
                                d[i][j]=-1001;
                        }
                }
        }

        for (int i=0; i<m; i++) {
                a=c[i][0];
                b=c[i][1];
                cout << d[a-1][b-1] << endl;
        }

        return 0;
}