#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct nod
{
 int c1,c2,cs;
};
int sort_nod(nod* a,nod* b)
{
 if (a->cs>b->cs)
  return -1;
 if (a->cs<b->cs)
  return 1;
 return 0;
}
int sort(const void* a,const void* b)
{
 return sort_nod((nod*)a,(nod*)b);
}
int main()
{
 nod a[6000];
 int i,j,n,nr=0,n1=0,n2=0,poz[128];
 long s1=0,s2=0;
 freopen("croco.in","r",stdin);
 scanf("%d\n",&n);
 for (i=0;i<n;i++)
  for (j=0;j<n;j++)
  {
   scanf("%d ",&a[nr].cs);
   if (i<j)
   {
    a[nr].c1=i;
    a[nr].c2=j;
    nr++;
   }
  }
 qsort((void*)a,nr,sizeof(a[0]),sort);
 int x=0;
 while (n1+n2<n&&n1<n-1)
 {
  if (poz[a[x].c1]&&!poz[a[x].c2])
  {
   poz[a[x].c2]=poz[a[x].c1];
   if (poz[a[x].c2]==1)
   {
    n1++;
    s1+=a[x].cs;
    for (i=0;i<nr;i++)
    {
     if (i!=x&&a[i].c1==a[x].c2&&poz[a[i].c2]==1)
      s1+=a[i].cs;
     if (i!=x&&a[i].c2==a[x].c2&&poz[a[i].c1]==1)
      s1+=a[i].cs;
    }
   }
   else
   {
    n2++;
    s2+=a[x].cs;
    for (i=0;i<nr;i++)
    {
     if (i!=x&&a[i].c1==a[x].c2&&poz[a[i].c2]==2)
      s2+=a[i].cs;
     if (i!=x&&a[i].c2==a[x].c2&&poz[a[i].c1]==2)
      s2+=a[i].cs;
    }
   }
  }
  else
   if (poz[a[x].c2]&&!poz[a[x].c1])
   {
    poz[a[x].c1]=poz[a[x].c2];
    if (poz[a[x].c1]==1)
    {
     n1++;
     s1+=a[x].cs;
     for (i=0;i<nr;i++)
     {
      if (i!=x&&a[i].c1==a[x].c1&&poz[a[i].c2]==1)
       s1+=a[i].cs;
      if (i!=x&&a[i].c2==a[x].c1&&poz[a[i].c1]==1)
       s1+=a[i].cs;
     }
    }
    else
    {
     n2++;
     s2+=a[x].cs;
     for (i=0;i<nr;i++)
     {
      if (i!=x&&a[i].c1==a[x].c1&&poz[a[i].c2]==2)
       s2+=a[i].cs;
      if (i!=x&&a[i].c2==a[x].c1&&poz[a[i].c1]==2)
       s2+=a[i].cs;
     }
    }
   }
   else
    if (!poz[a[x].c1]&&!poz[a[x].c2])
     if (!n1)
     {
      poz[a[x].c1]=poz[a[x].c2]=1;
      s1+=a[x].cs;
      n1+=2;
      for (i=0;i<nr;i++)
      {
       if (i!=x&&a[i].c1==a[x].c1&&poz[a[i].c2]==1)
        s1+=a[i].cs;
       if (i!=x&&a[i].c2==a[x].c1&&poz[a[i].c1]==1)
        s1+=a[i].cs;
       if (i!=x&&a[i].c1==a[x].c2&&poz[a[i].c2]==1)
        s1+=a[i].cs;
       if (i!=x&&a[i].c2==a[x].c2&&poz[a[i].c1]==1)
        s1+=a[i].cs;
      }
     }
     else
     {
      poz[a[x].c1]=poz[a[x].c2]=2;
      s2+=a[x].cs;
      n2+=2;
      for (i=0;i<nr;i++)
      {
       if (i!=x&&a[i].c1==a[x].c1&&poz[a[i].c2]==2)
        s2+=a[i].cs;
       if (i!=x&&a[i].c2==a[x].c1&&poz[a[i].c1]==2)
        s2+=a[i].cs;
       if (i!=x&&a[i].c1==a[x].c2&&poz[a[i].c2]==2)
        s2+=a[i].cs;
       if (i!=x&&a[i].c2==a[x].c2&&poz[a[i].c1]==2)
        s2+=a[i].cs;
      }
     }
  x++;
 }
 freopen("croco.out","w",stdout);
 printf("%d %d\n",(s1+s2),n1);
 for (i=0;i<n;i++)
  if (poz[i]==1)
   printf("%d ",(i+1));
 return 0;
}