#include <iostream>
#include<fstream>
using namespace std;
struct vecin;
struct varf;
struct vecin
{
    varf *vf;
    int cost;
    bool evidentiat;
    vecin(){cost=-1;vf=NULL;evidentiat=false;}
};

struct varf
{
    int id;
    int nr_vec;
    vecin **vecini;
    bool evidentiat;
    varf(){evidentiat=false;id=-1;nr_vec=-1;}
};

int main()
{
    int cost_minim = 0;
    bool DBG = true;
    ifstream f("graf.in");
    int n;
    f>>n;
    varf v[n];
    for(int i=0;i<n;i++)
    {
        v[i].id = i+1;
        f>>v[i].nr_vec;//nr de vecini al nodului
        v[i].vecini = new vecin*[v[i].nr_vec];
        for(int j=0;j<v[i].nr_vec;j++)
        {   int indx;
            f>>indx;
            v[i].vecini[j]=new vecin;
            v[i].vecini[j]->vf = &v[indx-1];
            f>>v[i].vecini[j]->cost;
        }
    }
if(DBG == true)
    {
        cout<<"\n";
        for(int i=0;i<n;i++)
            for(int j=0;j<v[i].nr_vec;j++)
            {
                cout<<"Drumul de la varful "<<v[i].id<<" la "<<v[i].vecini[j]->vf->id<<" costa "<<v[i].vecini[j]->cost;
                cout<<endl;
            }
    }
    cout<<"Introduceti nodul de plecare:";int x;cin>>x;
    v[x-1].evidentiat = true;
    int minc = 250000000;int y=0, z=0;
    for(int j=0;j<v[x-1].nr_vec;j++)
    {
        if(minc >= v[x-1].vecini[j]->cost)
        {
            minc = v[x-1].vecini[j]->cost;
            y=j;
        }
    }
    cost_minim = cost_minim + v[x-1].vecini[y]->cost;
    v[x-1].vecini[y]->evidentiat = true;
    v[x-1].vecini[y]->vf->evidentiat = true;
    for(int j=0;j<v[v[x-1].vecini[y]->vf->id-1].nr_vec;j++)
        if(v[v[x-1].vecini[y]->vf->id-1].vecini[j]->vf==&v[x-1])
            v[v[x-1].vecini[y]->vf->id-1].vecini[j]->evidentiat = true;
    cout<<"S-a evidentat nodul "<<v[x-1].vecini[y]->vf->id<<" si muchia "<<v[x-1].id<<"---"<<v[x-1].vecini[y]->vf->id<<" (cost "<<v[x-1].vecini[y]->cost<<")";
    while(true)
    {bool terminat = true;
        minc = 250000000;
        for(int i=0;i<n;i++)
        {
          if(v[i].evidentiat == true)
            for(int j=0;j<v[i].nr_vec;j++)
            {   if(v[i].vecini[j]->evidentiat == false && v[i].vecini[j]->vf->evidentiat == false)
                {terminat = false;
                    if(minc >= v[i].vecini[j]->cost)
                    {
                        minc=v[i].vecini[j]->cost;
                        y=j;
                        z=i;
                    }
                }
            }
        }
     if(terminat == true)
        break;
     cout<<endl<<"S-a evidentat nodul "<<v[z].vecini[y]->vf->id<<" si muchia "<<v[z].id<<"---"<<v[z].vecini[y]->vf->id<<" (cost "<<v[z].vecini[y]->cost<<")";
     v[z].vecini[y]->evidentiat = true;
     v[z].vecini[y]->vf->evidentiat = true;
     for(int j=0;j<v[v[z].vecini[y]->vf->id-1].nr_vec;j++)
        if(v[v[z].vecini[y]->vf->id-1].vecini[j]->vf == &v[z])
            v[v[z].vecini[y]->vf->id-1].vecini[j]->evidentiat = true;
     cost_minim = cost_minim + v[z].vecini[y]->cost;

    }
        cout<<"\nCostul minim e "<<cost_minim;
}