#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int t[200001],a[200001][2];
struct muchie
{
    int n1, n2, c;
}v[200001];
bool cmp(muchie a, muchie b)
{
    return a.c<=b.c;
}
int sef(int x)
{
    if(x!=t[x])
        t[x]=sef(t[x]);
    return t[x];
}
void join(int x, int y)
{
    int t1=sef(x);
    int t2=sef(y);
    t[t2]=t1;
}
int main()
{
    int n, m, x, y, z, cost=0, k=0, j;
    in>>n>>m;
    for(int i=1; i<=n; i++)
        t[i]=i;
    for(int i=1; i<=m; i++)
        in>>v[i].n1>>v[i].n2>>v[i].c;
    sort(v+1, v+m+1, cmp);
    for(int i=1; i<=m&&k<=n-1; i++)
    {
        if(sef(v[i].n1)!=sef(v[i].n2))
        {
            join(v[i].n1, v[i].n2);
            cost+=v[i].c;
            k++;
            a[k][0]=v[i].n1;
            a[k][1]=v[i].n2;
        }

    }
    cout<<cost<<endl<<n-1<<endl;
    for(int i=1; i<=n-1; i++)
        cout<<a[i][1]<<" "<<a[i][0]<<endl;
    return 0;
}