#include <bits/stdc++.h>
#define piii pair<int,pair<int,int> >
using namespace std;
int n,m,x,y,c,counter;
int parent[200005],val[200005];
priority_queue<piii,vector<piii >,greater<piii > >pq;
bitset<200005>ap;
vector<pair<int,int> >ans;
int find_parent(int pos)
{
    if(pos==parent[pos])
        return pos;
    return parent[pos]=find_parent(parent[pos]);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        pq.push({c,{x,y}});
    }
    for(int i=1;i<=n;i++)
    {
        val[i]=1;
        parent[i]=i;
    }
    while(ans.size()!=n-1)
    {
        int cost=pq.top().first;
        int first=pq.top().second.first;
        int second=pq.top().second.second;
        pq.pop();
        if(ap[first]==1 && ap[second]==1 && find_parent(first)==find_parent(second))
            continue;
        ap[first]=1;
        ap[second]=1;
        int parent1=find_parent(first);
        int parent2=find_parent(second);
        if(val[parent1]>=val[parent2])
        {
            val[parent1]+=val[parent2];
            parent[parent2]=parent1;
        }
        else
        {
            val[parent2]+=val[parent1];
            parent[parent1]=parent2;
        }
        ans.push_back({first,second});
        counter+=cost;
    }
    printf("%d\n%d",counter,n-1);
    for(int i=0;i<n-1;i++)
        printf("\n%d %d",ans[i].first,ans[i].second);
    return 0;
}