#include <bits/stdc++.h>
#define N 200001
#define M 400001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

vector<tuple<int,int,int>> v;
vector<pair<int,int>> sol;
int t[N],n,m,cost;

bool sort_(tuple<int,int,int> a,tuple<int,int,int> b)
{
    return get<2>(a)<get<2>(b);
}

int main()
{
    int i,a,b,ct,k;
    
    fin>>n>>m;
    
    for(i=0;i<m;i++)
    {
        fin>>a>>b>>ct;
        v.push_back(make_tuple(a,b,ct));
    }
    
    sort(v.begin(),v.end(),sort_);
    
    for(i=1;i<=n;i++)
        t[i]=i;
        
    k=0;
    while(sol.size()<n-1)
    {
        a=get<0>(v[k]);
        b=get<1>(v[k]);
        ct=get<2>(v[k]);
        k++;
        
        if(t[a]!=t[b])
        {
            cost+=ct;
            sol.push_back(make_pair(a,b));
            if(t[a]>t[b])
            {
                int aux=t[b];
                t[b]=t[a];
                t[a]=aux;
            }
            
            int val=t[b];
            
            for(i=1;i<=n;i++)
                if(t[i]==val)
                    t[i]=t[a];
        }
    }
    
    fout<<cost<<"\n";
    fout<<sol.size()<<"\n";
    
    for(i=0;i<sol.size();i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    
    return 0;
}