#include <bits/stdc++.h>
#define nmax 200001
#define mp make_pair
#define pb push_back
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
set<pair<int,pair<int,int>>> s,temp;
vector<pair<int,int>> sol;
int n,m,i,x,y,cost,v[nmax],n1,n2,k,c;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        s.insert(mp(cost,mp(x,y)));
    }
    cost=s.begin()->first;
    n1=s.begin()->second.first; n2=s.begin()->second.second; s.erase(s.begin());
    sol.pb(mp(n1,n2));
    v[n1]=v[n2]=1; k=1;
    while(k!=n-1)
    {
        auto it=s.begin();
        n1=it->second.first;
        n2=it->second.second;
        c=it->first;
        if(v[n1]+v[n2]==0)
        {
            it++;
            n1=it->second.first;
            n2=it->second.second;
            c=it->first;
        }
        //cout<<n1<<" "<<n2<<" "<<v[n1]<<" "<<v[n2]<<'\n';
        if(v[n1]+v[n2]==1)
        {
            k++;
            v[n1]=v[n2]=1;
            cost+=c;
            sol.pb(mp(n1,n2));
        }
        s.erase(it);
    }
    fout<<cost<<"\n"<<sol.size()<<"\n";
    for(auto it:sol)
        fout<<it.first<<" "<<it.second<<"\n";
    return 0;
}