/* Algoritmul lui Prim (determină un APM într-un graf ponderat conex) */ /* V.5 */
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int nr_vf, nr_eg;   // identificatorii "lungi" (in loc de n, m) evita confuzii la copiere!
ifstream fs("muchii.txt");
typedef struct A
{
    int beg,end1;
    double cost;
} muchie;
vector <A> M;
vector <int> za;
vector <int> APM;

void init()
{   A muchiee;
    int i;
    fs>>nr_vf>>nr_eg;
    for(i=0; i <nr_eg; i++ )
        M.push_back(muchiee);

    for (i = 0; i < nr_eg; i++)
    {
        fs>>M[i].beg;
        fs>>M[i].end1;
        fs>>M[i].cost;
        M[i].beg--;
        M[i].end1--;
    }
    for (i = 0; i < nr_vf; i++)
       {

        za.push_back(0) ;
        APM.push_back(0);

}
}

int cut_min()
{
    int rm;
    double q = 1.E15;
    for (int i = 0; i < nr_eg; i++)
        if(za[M[i].beg] !=za[M[i].end1])
            if(M[i].cost < q)
            {
                rm = i;
                q = M[i].cost;
            }
    return rm;
}

void apm_Prim(int start)
{
    za[start] = 1;
    for (int i = 0; i < nr_vf - 1; i++)
    {
        int rm = cut_min();
        APM[i] = rm; // muchia de rang rm este inclusa in APM (a i-a muchie a arborelui)
        if(za[M[rm].beg])
            za[M[rm].end1] = 1; // marcheaza si celalalt capat al muchiei incluse in APM
        else za[M[rm].beg] = 1;
    }
}
int main()
{
    double cost_apm = 0;
    int i;
    init();
    cout << "vârful de plecare: ";
    cin>>i;

    apm_Prim(i - 1);

    for (i = 0; i < nr_vf - 1; i++)   // afisare APM si cost
    {
        int rm = APM[i];
        cout << (M[rm].beg + 1) << " - " << (M[rm].end1 + 1) << '\t' << M[rm].cost << '\n';
        cost_apm += M[rm].cost;
    }
    cout << "\nCostul minim = " << cost_apm << '\n';
    fs.close();
    return 0;
}