#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
vector<pair<int,pair<int,int> > >v;
vector<pair<int,int> >s;
vector<int> C1,C2;
int n,m,i,T[200010],x,y,c,C,j;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    vector<pair<int,pair<int,int> > >::iterator it;
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d%d",&x,&y,&c);
        v.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(v.begin(),v.end());
    for(i=1;i<=n;i++)
        T[i]=i;
    for(it=v.begin();s.size()<n-1;it++)
    {
        x=it->second.first;
        y=it->second.second;
        c=it->first;
        for(i=x;i!=T[i];i=T[i])
            C1.push_back(i);
        for(j=y;j!=T[j];j=T[j])
            C2.push_back(j);
        if(i!=j)
        {
            s.push_back(make_pair(x,y));
            C+=c;
            T[j]=i;
        }
        for(;C1.size();C1.pop_back())
            T[C1.back()]=i;
        for(;C2.size();C2.pop_back())
            T[C2.back()]=i;
    }
    printf("%d\n%d\n",C,n-1);
    for(i=0;i<n-1;i++)
        printf("%d %d\n",s[i].first,s[i].second);
    return 0;
}