#include <fstream>
#include <vector>
#include <algorithm>
const int NMAX=200005;

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct trio
{
    int nod1,nod2,cost;

    bool operator <(const trio &other) const
    {
        ///(nod1 , nod2 , cost) < (other.nod1 , other.nod2 , other.cost)
        if(cost==other.cost)
        {
            if(nod1==other.nod1)
            {
                return (nod2<other.nod2);
            }
            return (nod1<other.nod1);
        }
        return (cost<other.cost);
    }
};

int n,m;
vector<trio> muchii;
vector<trio> ansMuchii;
vector<int> multimi[NMAX];
int from[NMAX];

bool areConnected(int a,int b)
{
    return (from[a]==from[b]);
}

void combine(int a,int b)
{
    if(multimi[a].size()<multimi[b].size()) swap(a,b);
    for(auto i:multimi[b])
    {
        multimi[a].push_back(i);
        from[i]=a;
    }
    multimi[b].clear();
    multimi[b].shrink_to_fit();
}

void init()
{
    for(int i=1;i<=n;i++)
    {
        multimi[i].push_back(i);
        from[i]=i;
    }
    sort(muchii.begin(),muchii.end());
}

void kruskal()
{
    int ans=0;
    init();
    for(auto i:muchii)
    {
        if(!areConnected(i.nod1,i.nod2))
        {
            combine(from[i.nod1],from[i.nod2]);
            ans+=i.cost;
            ansMuchii.push_back(i);
        }
    }
    cout<<ans<<endl;
    cout<<ansMuchii.size()<<endl;
    for(auto i:ansMuchii)
    {
        cout<<i.nod1<<" "<<i.nod2<<endl;
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int nod1,nod2,cost;
        cin>>nod1>>nod2>>cost;
        muchii.push_back({nod1,nod2,cost});
    }
    kruskal();
    return 0;
}