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

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

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

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

int caut(int x)
{
    if(x==t[x])
        return x;
    else
    {
        t[x]=caut(t[x]);
        return t[x];
    }
}


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