#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=310;
int n,m,a[N][N],dis[310],mk[310],ans;
struct edge {
	int dis,pos;
	bool operator <(const edge &o) const{
		return o.dis<dis;
	}
};
priority_queue<edge>q;
void dijkstra (int s,int p) {
	memset(mk,0,sizeof(mk));
	memset(dis,0x3f,sizeof(dis));
	q.push({0,s});
	dis[s]=0;
	while (!q.empty()) {
		edge t=q.top();
		q.pop();
		int u=t.pos;
		if (mk[u]==1) continue;
		mk[u]=1;
		for (int i=1;i<=n;i++) {
			if (i==u||i==p) continue;
			if (dis[u]+a[u][i]<dis[i]) {
				dis[i]=dis[u]+a[u][i];
				q.push({dis[i],i});
			}
		}
	}
}
int main () {
	freopen("hopeicanjump.in","r",stdin);
	freopen("hopeicanjump.out","w",stdout); 
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i=1;i<=n;i++) {
    	for (int j=1;j<=n;j++) {
    		cin >> a[i][j];
		}
	}
	while (m--) {
		int s,t,p;
		cin >> s >> t >> p;
		dijkstra(s,p);
		cout << dis[t] <<endl;
	}
    return 0;
}