#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
const int NMAX=400005;
int x[NMAX],y[NMAX],cost[NMAX],muchii[NMAX],t[NMAX];
vector<int>vans;
int n,m,suma;
bool cmp(int a, int b)
{
    return cost[a]<cost[b];
}
int grupa(int nod)
{
    if(t[nod]==nod)
        return nod;
    return t[nod]=grupa(t[nod]);
}
void uneste(int nod1, int nod2)
{
    int t1=grupa(nod1);
    int t2=grupa(nod2);
    t[t2]=t1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i]>>cost[i];
        muchii[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
    }
    sort(muchii+1,muchii+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(grupa(x[muchii[i]])!=grupa(y[muchii[i]]))
        {
            uneste(x[muchii[i]],y[muchii[i]]);
            vans.push_back(muchii[i]);
            suma+=cost[muchii[i]];
        }
    }
    cout<<suma<<'\n';
    cout<<vans.size()<<'\n';
    for(int i=0;i<vans.size();i++)
    {
        cout<<y[vans[i]]<<" "<<x[vans[i]]<<'\n';
    }
    return 0;
}