#include <bits/stdc++.h>
//#define pair<int,int> pr
//#define push_back pb
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int i,j,n,m,k,sum,cost,fx,fy,nod,x,y,c;
vector< pair< int, pair<int, int> > >  muchii;
vector< pair<int, int> > tata(10001);
vector< pair<int, int> > solutie;
bool check(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b)
{
    return a.second.second < b.second.second;
}
int find(int nod)
{
    if(tata[nod].first != nod)
        tata[nod].first = find(tata[nod].first);
    return tata[nod].first;
}
void merge(int x, int y)
{
    if(tata[x].second < tata[y].second)
        tata[x].first = y;
    else if(tata[x].second > tata[y].second)
        tata[y].first = x;
    else{
        tata[x].second++;
        tata[y].second = x;
    }
}
int main() {
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        tata[i] = make_pair(i, 0);
    }
    for(int i=0;i<m;i++)
    {
        f>>x>>y>>c;
        muchii.push_back(make_pair(x,make_pair(y,c)));
    }
    sort(muchii.begin(),muchii.end(),check);
    for(int i=0;i<m;i++)
    {
        x = muchii[i].first;
        y = muchii[i].second.first;
        cost = muchii[i].second.second;
        fx = find(x);
        fy = find(y);
        if(fy!=fx)
        {
            merge(fx,fy);
            solutie.push_back(make_pair(x,y));
            sum=sum+cost;
        }
    }
    g<<sum<<endl<<solutie.size()<<endl;
    for(int i=0;i<solutie.size();i++)
    {
        g<<solutie[i].first<<" "<<solutie[i].second<<endl;
    }

    return 0;
}