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

struct muchie {
                int x,y,cost;
              };

muchie a[1000];
int mk[40];

int main()
{
    ifstream fin("graf.in");
    int n,m,aux1,aux2,k,i,j,ct=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
     fin>>a[i].x>>a[i].y>>a[i].cost;
    for(i=1;i<m;i++)
      for(j=i+1;j<=m;j++)
        if(a[i].cost>a[j].cost) swap(a[i],a[j]);
    for(i=1;i<=n;i++)mk[i]=i;
    j=1;i=1;
    cout<<"Iata muchiile apm-ului:\n";
    while(j<=n-1)
    {
        ///verif. daca muchia a[i] poate fi aleasa
        if(mk[a[i].x]!=mk[a[i].y])
        {
            aux1=mk[a[i].y];//e marca PE care o inlocuiesc
            aux2=mk[a[i].x];//e marca CU care o inlocuiesc
            for(k=1;k<=n;k++)
                if(mk[k]==aux1)mk[k]=aux2;
            cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].cost<<"\n";
            ct+=a[i].cost;
            j++;
        }
        i++;
    }
    cout<<"Costul total al APM:"<<ct;
    return 0;
}