#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<int> sol[N];
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);
}

void dfs(int nod,int cautat,bool &gasit,int val)
{
    if(!gasit)
    {
        t[nod]=val;
        if(nod==cautat)
            gasit=true;
        else
            for(auto s:sol[nod])
                if(t[s]!=val)
                    dfs(s,cautat,gasit,val);
    }
}

int main()
{
    int i,a,b,ct,nr,k;
    bool gasit;
    
    fin>>n>>m;
    
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>ct;
        v.push_back(make_tuple(a,b,ct));
    }
    
    sort(v.begin(),v.end(),sort_);
    
    nr=k=0;
    
    while(nr<n-1)
    {
        a=get<0>(v[k]);
        b=get<1>(v[k]);
        ct=get<2>(v[k]);
        
        k++;
        gasit=false;
        
        dfs(a,b,gasit,k);
        
        if(!gasit)
        {
            sol[a].push_back(b);
            sol[b].push_back(a);
            cost+=ct;
            
            nr++;
        }
    }
    
    fout<<cost<<'\n'<<nr<<'\n';
    
    for(i=1;i<=n;i++)
        for(auto s:sol[i])
            if(i>s)
                fout<<i<<" "<<s<<'\n';
    return 0;
}