#include<iostream>
#include<fstream>
#include<cstdio>
#define INF 2000
using namespace std;
typedef long long ll;
ll a,b;
ll edge[5005][5005];
ll cost[5005];
ll vis[5005];
ll prim(){
	for(int i = 0;i<=b;i++){
		cost[i] = INF;
		vis[i] = 0;
	}
	ll mst = a;
	cost[1] = 0;
	for(int i = 1;i<=b;i++){
		ll index = 0;
		for(int j = 1;j<=b;j++){
			if(vis[j]==0&&cost[j]<cost[index]){
				index = j;
			}
		}
		cout << index << " " << cost[index] << endl;
		vis[index] = 1;
		mst+=cost[index];
		for(int j = 1;j<=b;j++){
			if(vis[j]==0&&cost[j]>edge[index][j]){
				cost[j] = edge[index][j];
			}
		}
	}
	return mst;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%lld%lld",&a,&b);
	for(int i = 1;i<=b;i++){
		for(int j = 1;j<=b;j++){
			scanf("%lld",&edge[i][j]);
			if(edge[i][j]>a) edge[i][j] = a;
		}
	}
	printf("%lld",prim());
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}