#include <bits/stdc++.h>

using namespace std;

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

int n,m,nrC;
vector<tuple <int,int,int>> muchie;
int unire[200001];
int unireS[200001];

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

int rad(int x)
{
    while(x!=unire[x])
        x=unire[x];

    return x;
}

int main()
{
    in>>n>>m;

    nrC=n;
    for(int i=1;i<=n;i++)
    {
        unire[i]=i;
        unireS[i]=1;
    }

    for(int i,j,cost,k=1;k<=m;k++)
    {
        in>>i>>j>>cost;
        muchie.push_back(make_tuple(cost,i,j));
    }

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

    int poz=0;
    while(nrC!=1)
    {
        int cost,a,b;
        tie(cost,a,b)=muchie[poz++];

        int ra=rad(a);
        int rb=rad(b);

        if(ra!=rb)
        {
            if(unireS[ra]<unireS[rb])
                swap(ra,rb);

            unire[rb]=ra;
            unireS[ra]+=unireS[rb];

            sol.push_back({a,b});
            ctot+=cost;
            nrC--;
        }
    }

    out<<ctot<<'\n'<<n-1<<'\n';

    for(auto a:sol)
        out<<a.first<<' '<<a.second<<'\n';

    return 0;
}