#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>>
using namespace std;

vector <int> p,h;

int FindSet(int u)
{
    if(p[u]==0)return u;
    p[u]=FindSet(p[u]);
    return p[u];
}

void Union(int u, int v)
{
    u=FindSet(u);
    v=FindSet(v);
    if(h[u]>h[v])p[v]=u;
    else
    {
        p[u]=v;
        if(h[u]==h[v])h[v]++;
    }
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,i,k,COST=0;
    pair<int ,pair <int,int> > m;
    f>>n>>k;
    set <pair<int ,pair <int,int> > > muchii;
    vector <pair<int ,pair <int,int> > > A;
    set <pair<int ,pair <int,int> > >::iterator it;

    for(i=0; i<k; i++)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        m.first=cost;
        m.second.first=x;
        m.second.second=y;
        muchii.insert(m);
    }
    f.close();

    for(i=0; i<n; i++)
    {
        p.push_back(0);
        h.push_back(0);
    }

    while(!muchii.empty())
    {
        it=muchii.begin();
        m=*it;
        if(FindSet(m.second.first)!=FindSet(m.second.second))
        {
            A.push_back(m);
            COST+=m.first;
            Union(m.second.first,m.second.second);
            if(A.size()==n-1)break;
        }
        muchii.erase(m);
    }

    g<<COST<<endl<<A.size()<<endl;
    for(i=0; i<A.size(); i++)
        g<<A[i].second.first<<" "<<A[i].second.second<<endl;
}