#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int N=200010;
int dad[N],x,y,cost,n,m,rx,ry,get_root(int),total;
vector<tuple<int,int,int>> v;
vector<pair<int,int> >sol;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)dad[i]=i;
    for(;m;m--)
    {
        fin>>x>>y>>cost;
        v.push_back(make_tuple(cost,x,y));
    }
    sort(v.begin(),v.end());
    for(auto it:v)
    {
        tie(cost,x,y)=it;
        rx=get_root(x);
        ry=get_root(y);
        if(rx==ry)continue;
        total+=cost;
        dad[rx]=ry;
        sol.push_back(make_pair(x,y));
        if(int(sol.size())==n-1)break;
    }
    fout<<total<<'\n'<<n-1<<'\n';
    for(auto it:sol)
    {
        fout<<it.first<<' '<<it.second<<'\n';
    }
    return 0;
}


int get_root(int nod)
{
    if(dad[nod]==nod)return nod;
    dad[nod]=get_root(dad[nod]);
    return dad[nod];
}