#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
typedef pair <int, int > P;
#define infinit 2000000000
#define max_el 200000
vector <P> v[max_el];
queue <P> Q;
int n,m,T[max_el],s[max_el],C,total;
ofstream g("apm.out");
void citire()
{
    int x,y,cost;
    ifstream f("apm.in");
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
        v[y].push_back(make_pair(x,cost));
    }
    f.close();
}
void afisare(int linie)
{
    int nr;
    nr=v[linie].size();
    for(int i=0; i<nr; i++)
        g<<v[linie][i].first<<" "<<v[linie][i].second<<endl;
    g<<endl;
}
int cauta(int linie,int second)
{
    int nl;
    nl=v[linie].size();
    for(int i=0; i<nl; i++)
        if(v[linie][i].first==second)
            return v[linie][i].second;
    return infinit;
}
void APM()
{
    int i,j,tata,fiu,ns=1,minim,cost,cost1;
    for(i=1; i<=n; i++)
        s[i]=1;
    s[ns]=0;
    for(i=1; i<n; i++)
    {
        tata=fiu=-1;
        minim=infinit;
        for(j=1; j<=n; j++)
            if(s[j]!=0)
            {
                cost=cauta(s[j],j);
                if(cost<minim)
                {
                    minim=cost;
                    tata=s[j];
                    fiu=j;
                }
            }

        Q.push(make_pair(tata,fiu));

        T[fiu]=tata;
        s[fiu]=0;
        C=C+minim;
        for(j=1; j<=n; j++)
            if(s[j]!=0)
            {

                cost=cauta(s[j],j);
                cost1=cauta(fiu,j);
                if((cost>cost1)||(cost==infinit&&cost1!=infinit))
                    s[j]=fiu, s[fiu]=0;

            }
    }

}
int main()
{
    citire();
    APM();
    g<<C;
    g<<'\n'<<n-1<<'\n';
    while(!Q.empty())
    {
        g<<Q.front().first<<" "<<Q.front().second<<'\n';
        Q.pop();
    }
    g.close();
    return 0;
}