#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,s,m;
const int N=2e5+3;
const int M=4e5+3;
queue<pair<int,int>>q;
struct nod
{
    int x,y,cost;
}a[M];
int tt[N],sz[N];
bool comp(nod X,nod Y)
{
    return X.cost<Y.cost;
}
int get_root(int X)
{
    if(X!=tt[X])
        return tt[X]=get_root(tt[X]);
    return X;
}
void _unite(int X,int Y)
{
    if(sz[X]>=sz[Y])
    {
        tt[Y]=X;
        sz[X]+=sz[Y];
    }
    else
    {
        tt[X]=Y;
        sz[Y]+=sz[X];
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].cost;
    }
    sort(a+1,a+m+1,comp);
    for(int i=1;i<=n;i++)
        tt[i]=i,sz[i]=1;
    for(int i=1;i<=m;i++)
    {
        int X=get_root(a[i].x);
        int Y=get_root(a[i].y);
        if(X!=Y)
        {
            q.push({X,Y});
            s+=a[i].cost;
            _unite(X,Y);
        }
    }
    g<<s<<'\n'<<q.size()<<'\n';
    while(!q.empty())
    {
        g<<q.front().first<<" "<<q.front().second<<'\n';
        q.pop();
    }
    return 0;
}