#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int Nmax=200005;
int p[Nmax];
pair<int,int> a[Nmax];
vector<pair<int,int>> m;
vector<int> sol;
int sef(int x)
{
    if(p[x]==x)
    {
        return x;
    }
    p[x]=sef(p[x]);
    return p[x];
}
int main()
{
    int n,k,x,y,c;
    fin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    for(int i=1;i<=k;i++)
    {
        fin>>x>>y>>c;
        a[i]={x,y};
        m.push_back({c,i});
    }
    sort(m.begin(),m.end());
    int nr=0;
    int sum=0;
    for(int i=0;nr<n-1;i++)
    {
        int sef1=sef(a[m[i].second].first);
        int sef2=sef(a[m[i].second].second);
        if(sef1!=sef2)
        {
            nr++;
            sol.push_back(m[i].second);
            sum+=m[i].first;
            p[sef2]=sef1;
        }
    }
    fout<<sum<<'\n';
    fout<<sol.size()<<'\n';
    for(int i=0;i<sol.size();i++)
    {
        fout<<a[sol[i]].first<<' '<<a[sol[i]].second<<'\n';
    }
    return 0;
}