#include <bits/stdc++.h>

using namespace std;

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

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

vector<pair<int,int>> tree;
int costTot;

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

    return x;
}

void uneste(int a,int b)
{
    int r1=rad(a);
    int r2=rad(b);

    if(unireS[r1]<unireS[r2])
        swap(r1,r2);

    unire[r2]=r1;
    unireS[r1]+=unireS[r2];
}

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

    nrComp=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(nrComp!=1)
    {
        int cost,a,b;
        tie(cost,a,b)=muchie[poz++];

        if(rad(a)!=rad(b))
        {
            uneste(a,b);

            tree.push_back({a,b});
            costTot+=cost;
            nrComp--;
        }
    }

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

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

    return 0;
}