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

using namespace std;

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

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

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

vector<int>sol;

bool 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 false;

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

    return true;

}

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)));
    }

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

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

    /**for(int i=0;i<m;++i)
    {

        g<<muchii[i].first<<" "<<muchii[i].second.first<<" "<<muchii[i].second.second<<'\n';

    }*/

    int i=0,ctotal=0,k=n-1;

    while(k)
    {

        if(muchie(muchii[i].second.first,muchii[i].second.second))
        {

            ctotal+=muchii[i].first;
            sol.push_back(i);
            k--;

        }
        ++i;
    }

    g<<ctotal<<'\n'<<n-1<<'\n';

    for(int i=0;i<sol.size();++i)
    {
        g<<muchii[sol[i]].second.first<<" "<<muchii[sol[i]].second.second<<'\n';
    }

    return 0;
}