#include <bits/stdc++.h>
#define maxm 400001
#define maxn 200001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,total;
int x[maxm],y[maxm],cost[maxm],tt[maxn],rg[maxn],ind[maxm];
vector<int> ans;

void Read()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        tt[i] = i;
        rg[i] = 1;
    }
    for(int i=1;i<=m;++i)
        {
            f>>x[i]>>y[i]>>cost[i];
            ind[i] = i;
        }
}

bool cmp(int i,int j)
{
    return cost[i] < cost[j];
}

int find(int x)
{
    int R,y;

    for(R = x;tt[R] != R;R = tt[R]);

    for(;tt[x] != x;)
    {
        y = tt[x];
        tt[x] = R;
        x = y;
    }

    return R;
}

void unite(int x,int y)
{
    if(rg[x] > rg[y])
        tt[y] = x;
    else tt[x] = y;

    if(rg[x] == rg[y]) ++rg[y];
}

void CreateAPM()
{
    sort(ind + 1, ind + m + 1,cmp);
    for(int i=1;i<=m;++i)
        if(find(x[ind[i]]) != find(y[ind[i]]))
        {
            total += cost[ind[i]];
            unite(find(x[ind[i]]),find(y[ind[i]]));
            ans.push_back(ind[i]);
        }
}

void Print()
{
    g<<total<<'\n';
    g<<ans.size()<<'\n';
    for(vector<int>::iterator it=ans.begin();it!=ans.end();++it)
        g<<x[*it]<<" "<<y[*it]<<'\n';
}

int main()
{
    Read();
    CreateAPM();
    Print();
    return 0;
}