#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 200001
ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,i,j,gr[MAXN],cost,crt,x,y,c;
bool fol[MAXN];
vector< pair< int, pair <int, int > > > graf;


int grupa(int nr)
{
    if(gr[nr]==nr)
        return nr;
    gr[nr]=grupa(gr[nr]);
    return gr[nr];
}

int reuniune(int a, int b)
{
    gr[grupa(a)] = grupa(b);
}
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        graf.push_back(make_pair(c, make_pair(x,y)));
    }

    sort(graf.begin(), graf.end());

    for(i=1; i<=n; i++)
        gr[i]=i;


    for(i=0; i<m; i++)
    {
        if(grupa(graf[i].second.first) != grupa(graf[i].second.second))
        {
            reuniune(graf[i].second.first, graf[i].second.second);
            cost+=graf[i].first;
            crt++; fol[i]=true;
        }
        if(crt==n-1)
            break;
    }
    cout<<cost<<"\n";
    cout<<n-1<<"\n";
    for(i=1; i<=m; i++)
        if(fol[i])
            cout<<graf[i].second.first<<" "<<graf[i].second.second<<"\n";
}