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

using namespace std;

pair<int,pair<int,int> > muchii[100007];
vector<pair<int,int> > apm;
int tata[100007],grad[100007];

int find_father(int nod)
{
    if(tata[nod]==nod)
        return nod;
    tata[nod]=find_father(tata[nod]);
    return tata[nod];
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,m,s=0,k=0;
    f>>n>>m;
    int a,b,c;
    for(int i=1; i<=n; i++)
    {
        tata[i]=i;
        grad[i]=1;
    }
    for(int i=1; i<=m; i++)
    {
        f>>a>>b>>c;
        muchii[i]=make_pair(c,make_pair(a,b));
    }
    sort(muchii+1,muchii+m+1);
    for(int i=1; i<=m; i++)
    {
        a=muchii[i].second.first;
        b=muchii[i].second.second;
            if(find_father(a)!=find_father(b))
            {

                int A=find_father(a);
                int B=find_father(b);
                if(grad[A]<grad[B])
                {
                    tata[A]=B;
                    grad[B]+=grad[A];
                }
                else
                {
                    tata[B]=A;
                    grad[A]+=grad[B];
                }
                s=s+muchii[i].first;
                k++;
                apm.push_back(make_pair(a,b));
            }
        }
    g<<s<<"\n";
    g<<k<<"\n";
    for(int i=0;i<k;i++)
        g<<apm[i].first<<" "<<apm[i].second<<"\n";
    return 0;
}