#include <bits/stdc++.h>
#define NMAX 200001
#define MMAX 400001
#define ff first
#define ss second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
int x[MMAX],y[MMAX],cost[MMAX],ind[MMAX],gr[MMAX],sol;
vector < pair<int, int> >v;
int root(int x)
{
    int r,y;
    for(r=x;r!=gr[r];r=gr[r]);
    while(x!=gr[x])
    {
        y=gr[x];
        gr[x]=r;
        x=y;
    }
    return r;
}
void unite(int x, int y)
{
    gr[x]=y;
}
bool comp(int i, int j)
{
    return (cost[i]<cost[j]);
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x[i]>>y[i]>>cost[i];
        ind[i]=i;
    }
    for(int i=1;i<=n;++i)gr[i]=i;
    sort(ind +1, ind + m+ 1, comp);
    for(int i=1;i<=m;++i)
    {
        int rx=root(x[ind[i]]);
        int ry=root(y[ind[i]]);
        if(rx!=ry)
        {
            sol+=cost[ind[i]];
            unite(rx,ry);
            v.push_back({x[ind[i]],y[ind[i]]});

        }

    }
    fout<<sol<<"\n";
    fout<<n-1<<"\n";
    for(auto x: v)
        fout<<x.ff<<" "<<x.ss<<"\n";

    return 0;
}