#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <math.h>

using namespace std;

class Field
{

};


int Min(int **tab, int N);
void Size(int &N);
void Read(int **tab, vector<int> &PC);
void Write(int **tab, int N);
void PrintScreen(int **tab, int N);
void Prim(int **tab, int **result, int N);
string Binary(int N);

int main()
{
    int N = 0;
    Size(N);

int ** tab;
tab = new int *[ N ];
for( int i = 0; i < N; i++ )
     tab[ i ] = new int[ N ];

    vector<int> PC;

    Read(tab, PC);
    PrintScreen(tab, N);

int **result;//0 - czy odwiedzony, 1 - poprzednik, 2 -wartość
result = new int *[ 3 ];
for( int i = 0; i < 3; i++ )
    result[ i ] = new int[ N ];


int ** tab2;
tab2 = new int *[ N ];
for( int i = 0; i < N; i++ )
     tab2[ i ] = new int[ N ];

int **result2;//0 - czy odwiedzony, 1 - poprzednik, 2 -wartość
result2 = new int *[ 3 ];
for( int i = 0; i < 3; i++ )
    result2[ i ] = new int[ N ];

//kopiowanie
for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
        tab2[i][j] = tab[i][j];

int SUMA = 16;
for(int p = 0; p < pow(2, N); p++)
{

    string binary = Binary(p);

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            {
                tab[i][j] = tab2[i][j];
                for(int x = 0; x < PC.size(); x++)
                if ((binary[i] == 0 || binary[j]==0 ) &&i!=x &&j!=x) {tab[i][j] = 0;}
            }

    for(int i = 0; i < N; i++){
        result[0][i] = 0;
        result[1][i] = 0;
        result[2][i] = INT_MAX;
        }
        Prim(tab, result, N);
        unsigned int suma = 0;
        for(int i = 0; i < N; i++){
            if(result[2][i] != INT_MAX) suma += result[2][i];
        }


        if(suma<SUMA)
        {
            cout<<p<<" "<<binary<<" Suma: "<<suma<<" "<< SUMA<<endl<<endl;

            Write(result, N);
        }
        SUMA = suma;
}

Write(result, N);

//zwalnianie pamiêci
for( int i = 0; i < N; i++ )
     delete[] tab[ i ];
delete[]tab;

for( int i = 0; i < 3; i++ )
     delete[] result[ i ];
delete[]result;

for( int i = 0; i < N; i++ )
     delete[] tab2[ i ];
delete[]tab2;

for( int i = 0; i < 3; i++ )
     delete[] result2[ i ];
delete[]result2;

    return 0;
}



void Size(int &N){
     fstream file;
    file.open( "MC_Deby_XII_in.txt", std::ios::in | std::ios::out);
    if( file.good() )
    {
        file>>N;
        file.close();
    }
    else cout<<"Nie udalo sie otworzyc pliku\n";

}
void Read(int **tab, vector<int> &PC){
  fstream file;
    file.open( "MC_Deby_XII_in.txt", std::ios::in | std::ios::out);
   if( file.good() )
    {
        int N;
        file>>N;
        int pc;
        file>>pc;
        for(int i = 0; i < pc; i++)
        {
            int h;
            file>>h;
            PC.push_back(h);
        }

        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                int h;
                file>>h;
                if(h != 300) tab[i][j] = h;
                else tab[i][j] = 0;
                if (i == j) tab[i][j] = 0; //pętle
            }
        }
        file.close();
    }
    else cout<<"Nie udalo sie otworzyc pliku\n";
}


void Write(int **result, int N){
  fstream file;
    file.open( "MC_Deby_XII_out.txt", std::ios::trunc | std::ios::in | std::ios::out);
   if( file.good() )
    {
         cout<<N-1<<endl;
         file<<N-1<<endl;
         for(int i = 1; i < N; i++){
            cout<<i+1<<" "<<result[1][i]+1<<endl;
            file<<i+1<<" "<<result[1][i]+1<<endl;
        }
    }
    else cout<<"Nie udalo sie otworzyc pliku\n";
}
void PrintScreen(int **tab, int N)
{
    for(int i = 0; i < N; i ++)
    {
        for(int j = 0; j < N; j ++)
        cout<<tab[i][j]<<"  ";
        cout<<endl;
    }
}


int Min(int **tab, int N)
{
    int tmp = INT_MAX;
    int index = 0;
    for(int i = 0; i < N; i++)
    {
        if(tmp >= tab[2][i] && tab[0][i]==0) {
            tmp = tab[2][i];
            index = i;
        }
    }
    return index;
}


string Binary(int N){
    string binary;
    while(N > 0)
    {
        int tmp = N%2;
        if(tmp==1) binary+='1';
            else binary+='0';
        N /= 2;
    }
    return binary;
}


void Prim(int **tab, int **result, int N)
{
    int tmp = 0;
    for(int i = 0; i < N; i++)
    {
         for(int j = 0; j < N; j++){
            if (tab[tmp][j]!=0 && result[0][j]==0 && tab[tmp][j]<result[2][j]){
                result[1][j] = tmp;
                result[2][j] = tab[tmp][j];
            }
         }
        result[0][tmp] = 1;
        tmp = Min(result, N);
    }
}