#include <bits/stdc++.h>
#define piii pair<int,pair<int,int> >
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int,int> >ans;
int n,m,x,y,c,counter;
int parent[200005],val[200005];
bool ap[200005];
priority_queue<piii,vector<piii >,greater<piii > >pq;
int find_parent(int pos)
{
    if(parent[pos]==pos)return pos;
    parent[pos]=find_parent(parent[pos]);
    return parent[pos];
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        pq.push({c,{x,y}});
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
        val[i]=1;
    }
    while(!pq.empty() && ans.size()!=n-1)
    {
        c=pq.top().first;
        x=pq.top().second.first;
        y=pq.top().second.second;
        pq.pop();
        if(ap[x]==1 && ap[y]==1 && find_parent(x)==find_parent(y))continue;
        ans.push_back({x,y});
        ap[x]=1;
        ap[y]=1;
        x=find_parent(x);
        y=find_parent(y);
        if(val[x]>val[y])
        {
            parent[y]=x;
            val[x]+=val[y];
        }
        else
        {
            parent[x]=y;
            val[y]+=val[x];
        }
        counter+=c;
    }
    fout<<counter<<"\n";
    fout<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
        fout<<ans[i].first<<" "<<ans[i].second<<"\n";
    return 0;
}