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

using namespace std;

pair<int,pair<int,int> > muchii[400005];
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;
}