#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1005;
const ll M  = 1e6+5;
ll n;
ll mp[N][N];
ll head[M], cnt;
struct node {
	ll to, nxt, dis;
} edge[M * 2];
ll ys(ll i, ll j) {
	return (i - 1) * n + j;
}
ll vis[N];
void add(ll from, ll to, ll dis) {
	cout << from << ' ' << to << " " << dis << '\n';
	cnt++;
	edge[cnt].dis = dis;
	edge[cnt].to = to;
	edge[cnt].nxt = head[from];
	head[from] = cnt;
}
int main() {
	cin >> n;
	for (ll i = 1; i <= n; i++)
		for (ll j = 1; j <= n; j++)
			cin >> mp[i][j];
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= n; j++) {
			if (i > 1) {
				add(ys(i, j), ys(i - 1, j), abs(mp[i][j] - mp[i - 1][j]));
			}
			if (j > 1) {
				add(ys(i, j), ys(i, j - 1), abs(mp[i][j] - mp[i][j - 1]));
			}
			if (i < n) {
				add(ys(i, j), ys(i + 1, j), abs(mp[i][j] - mp[i + 1][j]));
			}
			if (j < n) {
				add(ys(i, j), ys(i, j + 1), abs(mp[i][j] - mp[i][j + 1]));
			}
		}
	}
	ll NN = n * n / 2 + (n % 2 == 0);
	NN ^= 1;
//	cout <<a;
	priority_queue<pair<ll, ll > >q;
	q.push(make_pair(0, 1));
	ll MST = 0;
	ll tot = 0;
	while (q.size()) {
		ll x = q.top().second;
		ll v = q.top().first;
		q.pop();
		if (vis[x])continue;
		vis[x] = 1;
//		cout<<x<<" ";
		MST = max(MST, -v);
		tot++;
		if (tot == NN) {
			cout << MST;
			return 0;
		}
		for (ll i = head[x]; i; i = edge[i].nxt) {
			ll y = edge[i].to;
			ll d = edge[i].dis;
			if (!vis[y]) {
				q.push(make_pair(-d, y));
			}
		}
	}
	return 0;
}