#include <iostream>
#include <fstream>
using namespace std;

//Catrinoiu Ionut Bogdan, 131 - APM Prim

int cost[30][30], s[30], n, m;

struct muchie
{
    int m1,m2, c;
}v[30];


void apm_prim()
{
    int i,j,k,minim,a,b;
    s[1]=1;
    for (i=1;i<n;i++)
        {
          minim=32000;
    for(j=1;j<n;j++)
        for (k=j+1;k<=n;k++) //det muchia de cost min. cu o extr. in arb. si cealalta in afara
           if (s[j]+s[k]==1 && cost[j][k]!=0 && cost[j][k]<minim)
             {
                minim=cost[j][k];
                a=j;
                b=k;

             }

             //retinem muchia
             v[i].m1=a;
             v[i].m2=b;
             v[i].c=cost[a][b];


             s[a]=1; //nodul a face parte din arb.
             s[b]=1; //nodul b face parte din arb.


        }
}



int main()
{
    int i,t, tot_cost=0;
   //citire();

    ifstream fin("apm.in");
    int x,y;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>t;
        cost[x][y]=t;
        cost[y][x]=cost[x][y];
    }


    apm_prim();

    cout<<"MUCHII APM (PRIM): "<<endl;
    for (i=1;i<n;i++)
    {
        tot_cost+=v[i].c;
        cout<<v[i].m1<<" - "<<v[i].m2<<" COST "<<v[i].c<<endl;
    }

    cout<<"TOTAL COSTURI: "<<tot_cost<<endl;
  getchar();
    return 0;
}