/* Use Prim's algorithm, just to be different */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
/* A utility function to find the vertex with minimum key value from
   the set of vertices not yet included in MST */
int minKey(int *key, int* mstSet, int V)
{ int v, min = INT_MAX, min_index;
  for (int v = 0; v < V; v++)
    if (!mstSet[v] && key[v] < min)
      min = key[v], min_index = v;
  return min_index;
}
/* Function to construct MST using adjacency matrix representation */
int *primMST(int **graph, int V)
{
  int *parent = malloc(sizeof(int)*V);
  int *key = malloc(sizeof(int)*V);
  int *mstSet = malloc(sizeof(int)*V);
  int i,u,v;
  for (i = 0; i < V; i++)
    {
      key[i] = INT_MAX;/* Initialize all keys as INFINITE */
      mstSet[i] = 0;   /* and all nodes as not in the set */
    }
  key[0] = 0;     /* Make key 0 so that this vertex is picked as first vertex*/
  parent[0] = -1; /* First node is always root of MST */
  for (i = 0; i < V-1; i++)
    {
      u = minKey(key, mstSet, V);/* Pick the minimum key vertex */
      mstSet[u] = 1; /* Add the picked vertex to the MST Set */
      /* Update key value and parent index of the adjacent vertices of
         the picked vertex. Consider only those vertices which are not
         yet included in MST. graph[u][v] is non zero only for
         adjacent vertices of m mstSet[v] is false for vertices not
         yet included in MST Update the key only if graph[u][v] is
         smaller than key[v] */
      for (v = 0; v < V; v++)
	if (graph[u][v] && !mstSet[v] && graph[u][v] <  key[v])
	  parent[v]  = u, key[v] = graph[u][v];
    }
  free(key);
  free(mstSet);
  return parent;
}
int main()
{
  int i,j,N;
  int **cost,*parent;
  srand(time(NULL));
  scanf("%d",&N);
  cost = malloc(sizeof(int*)*N);
  for(i=0;i<N;i++)
    {
      cost[i] = malloc(sizeof(int)*N);
      for(j=0;j<N;j++)
	scanf("%d",&(cost[i][j]));
      if(cost[i][j] == 0)
	cost[i][j] = INT_MAX;
    }
  parent=primMST(cost,N);
  for (i = 1; i < N; i++)
    if((rand() >> 12)&1) // randomize order to test ouput validator
      printf("%d %d\n", i+1, parent[i]+1);
    else
      printf("%d %d\n", parent[i]+1, i+1);
  return 0;
}