#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m;

long long sum;
vector<int> sol;

struct elem{
int x;
int y;
int cost;
}v[400005];

bool cmp(elem a,elem b)
{
    return a.cost<b.cost;
}


int t[200005];
int rad(int x)
{
    int aux = x;
    while(t[aux]>0)
    {
        aux=t[aux];
    }
    int r = aux;
    while(t[x]>0)
    {
        int tmp = t[x];
        t[x]=r;
        x=tmp;
    }
    return r;
}
bool can_join(int x,int y)
{
    int rx= rad(x);
    int ry= rad(y);
    if(rx==ry)
        return 0; /// sunt deja legate
    if(-t[rx]>-t[ry])
    {
        t[rx]+=t[ry];
        t[ry]=rx;
    }
    else
    {
        t[ry]+=t[rx];
        t[rx]=ry;
    }
    return 1;
}


int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(can_join(v[i].x,v[i].y))
        {
            sum+=v[i].cost;
            sol.push_back(i);
        }
    }
    int sz = sol.size();
    fout<<sum<<'\n'<<sz<<'\n';
    for(int i=0;i<sz;i++)
    {
        fout<<v[sol[i]].x<<' '<<v[sol[i]].y<<'\n';
    }
}