#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct ceva
{
    int c,x,y;
}a[400005];
struct efectiv_ceva
{
    int x,y;
}sol[200003];
int n,m,x,y,c,t[200003],nr,solutie;
long long s;
bool cmp(ceva X,ceva Y)
{
    if(X.c<Y.c)return true;
    else return false;
}
int tata(int X)
{
    if(t[X]!=X)X=tata(t[X]);
    return X;
}
void tati(int X,int Y)
{
    X=tata(t[X]);
    Y=tata(t[Y]);
    t[Y]=t[X];
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
    }
    for(int i=1;i<=m && nr<=n-1;i++)
    {
        if(tata(t[a[i].x])!=tata(t[a[i].y]))
        {
            nr++;
            s=s+a[i].c;
            sol[nr].x=a[i].x;
            sol[nr].y=a[i].y;
            tati(a[i].x,a[i].y);
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+m+1,cmp);
    solve();
    g<<s<<'\n'<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        g<<sol[i].x<<" "<<sol[i].y<<'\n';
    }
    return 0;
}