#include <fstream>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector< pair<int, pair<int,int> > >muchii;
vector<pair<int,int> > sol;

int n,m,cost,t[200001],h[200001];

int muchie(int x,int y)
{

    int r1,r2,x1,y1,c;
    r1=x;r2=y;
    while (r1!=t[r1]) r1=t[r1];
    while (r2!=t[r2]) r2=t[r2];

    while (t[x]!=r1) {x1=t[x];t[x]=t[x1];x=x1;}
    while (t[y]!=r2) {y1=t[y];t[y]=t[y1];y=y1;}

    if (r1==r2) return 0;

    if (h[r1]>h[r2]) {t[r2]=r1;c=r1;}
        else {t[r1]=r2;c=r2;}
    if (h[r1]==h[r2]) h[c]++;

return 1;

}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {

        int x,y,c;
        f>>x>>y>>c;
        muchii.push_back(make_pair(c,make_pair(x,y)));

    }

    sort(muchii.begin(),muchii.end());

    for(int i=1;i<=n;++i)
    {
        t[i]=i;
        h[i]=1;
    }

    for(auto it=muchii.begin();it!=muchii.end()&&sol.size()<n-1;++it)
    {

        if(muchie((*it).second.first,(*it).second.second) )
        {

            cost+=(*it).first;
            sol.push_back(make_pair((*it).second.first,(*it).second.second));
        }

    }
    g<<cost<<'\n'<<n-1<<'\n';

    for(int i=0;i<n-1;++i)
        g<<sol[i].first<<" "<<sol[i].second<<'\n';

    return 0;
}