#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
int viz[200001];
class graf
{   int n , m,c;
    vector <pair<int,int> > A[100];
public:
    void fminim(int i,int &minim, int  &k)
    {   int j ;
        for(j=0;j<A[i].size();j++)
            if(A[i][j].second<minim && viz[A[i][j].first]==0)
            {minim=A[i][j].second;
            k=A[i][j].first;
            }

    }
    void citire(char *numfis)
    {  int i;
        ifstream f(numfis);
        f>>n;
        f>>m;
        for(i=0;i<m;i++)
        {   int a ,b,c;
            f>>a>>b>>c;
            A[a].push_back(make_pair(b,c));
            A[b].push_back(make_pair(a,c));
        }
    }
    void afisare()
    {  int i , j;
        for(i=1;i<=n;i++)
        {   cout<<endl<<i<<": ";
            for(j=0;j<A[i].size();j++)
                cout<<A[i][j].first<<" ";
        }
    }
    void prim()
    {
       graf A;
       int vizitati[200001];
       int l=1;
       vizitati[0]=1;
       A.n=1;
       int i=1,minim,k,p=0;
       viz[i]=1;
       while(A.n!=this->n)
       {
            minim=10000;
            for(int x=0;x<l;x++)
           this->fminim(vizitati[x],minim,k);

           A.A[i].push_back(make_pair(k,minim));
           i=k;
           viz[k]=1;
           vizitati[l++]=k;
           A.n++;
           A.m++;
           p=p+minim;
       }
       A.c=c;
       A.afisareapm();
    }
    void afisareapm()
    {   int i , j;
        ofstream g("apm.out");
        g<<c<<endl;
        g<<m<<endl;
        for(i=1;i<=n;i++)
            for(j=0;j<A[i].size();j++)
        {
            g<<i<<" "<<A[i][j].first;
            g<<endl;
        }

    }
};

int main()
{   graf G;
    ifstream f("apm.in");
    G.citire("apm.in");

    G.prim();
}