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

ifstream fin("disjoint.in");
ofstream fout("disjoint.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 caut(int x)
{
    if(x==t[x])
        return x;
    else
    {
        t[x]=caut(t[x]);
        return t[x];
    }
}

int main()
{
    int a,b,ct,i,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=0;
    
    while(sol.size()<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(t[A]!=t[B])
        {
            t[A]=B;
            cost+=ct;
            
            sol.push_back(make_pair(a,b));
        }
    }
    
    fout<<cost<<'\n'<<sol.size()<<'\n';
    for(auto s:sol)
        fout<<s.first<<" "<<s.second<<endl;
    return 0;
}