#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;
const int maxn = 3000 + 10;
int n;
int dp[maxn], d[maxn][maxn], par[maxn], dis[maxn][maxn];
bool mark[maxn];
int c[maxn], cnt = 1;
vector<int> t[maxn];
void dfs(int v){
mark[v] = 1;
int w = -1;
for (int u = 1; u <= n; u++)
if (mark[u] and d[v][u] == d[par[v]][u] and (w == -1 or dis[v][u] < dis[v][w]))
w = u;
if (w == -1)
c[v] = cnt ++;
else
c[v] = c[w];
for (auto u : t[v])
if (u != par[v])
dfs(u);
}
void DFS(int v, int root, int p = -1){
for (auto u : t[v])
if (u != p)
dis[root][u] = dis[root][v] + 1, DFS(u, root, v);
}
int main(){
ios_base::sync_with_stdio(false);
int chert;
cin >> chert >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> d[i][j];
memset(dp, 63, sizeof dp);
dp[1] = 0;
for (int _ = 1; _ <= n; _++){
int v = -1;
for (int u = 1; u <= n; u++)
if (!mark[u] and (v == -1 or dp[u] < dp[v]))
v = u;
if (v != 1){
t[par[v]].push_back(v);
t[v].push_back(par[v]);
}
mark[v] = 1;
for (int u = 1; u <= n; u++)
if (!mark[u] and dp[u] > d[u][v])
dp[u] = d[u][v], par[u] = v;
}
for (int v = 1; v <= n; v++)
dis[v][v] = 1, DFS(v, v);
memset(mark, 0, sizeof mark);
dfs(1);
for (int i = 1; i <= n; i++)
cout << c[i] << " \n"[i == n];
for (int i = 2; i <= n; i++)
cout << par[i] << " " << i << endl;
}
