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

#define nMax 200002
#define mMax 400004
#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define piii pair<int, pii>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, apmCost;
int Root[nMax];
vector<pair<int, int> > Sol;
piii Edge[mMax];
void read()
{
    int a, b, c;
    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        Edge[i]=mkp(c, mkp(a, b));
    }
}
int getRoot(int node)
{
    return (Root[node]<0 ? node : Root[node]=getRoot(Root[node]));
}
void solve()
{
    sort(Edge+1, Edge+m+1);
    for(int i=1;i<=n;i++)
        Root[i]=-1;

    for(int i=1;i<=m;i++)
    {
        int val1=getRoot(Edge[i].second.first), val2=getRoot(Edge[i].second.second);

        if(val1!=val2)
        {
            switch(Root[val1]-Root[val2]<0)
            {
                case 1:Root[val1]+=Root[val2];Root[val2]=val1;break;
                case 0:Root[val2]+=Root[val1];Root[val1]=val2;break;
            }
            apmCost+=Edge[i].first;
            Sol.pb(mkp(Edge[i].second.first, Edge[i].second.second));
        }
    }
}
void write()
{
    fout<<apmCost<<'\n'<<Sol.size()<<'\n';

    for(vector<pair<int, int> >::iterator it=Sol.begin();it!=Sol.end();it++)
        fout<<it->first<<" "<<it->second<<'\n';
}
int main()
{
    read();
    solve();
    write();
    return 0;
}