#include <bits/stdc++.h>
#define PII pair<int,int>
#define TIII tuple<int,int,int>
#define Cost first
#define Nod second

using namespace std;

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

int n,m;
vector <PII> gf[200001];
priority_queue <TIII,vector<TIII>,greater<TIII>> c;
bitset <200001> viz;
vector <PII> sol;
int costTot;

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

    for(int i,j,cost,k=1;k<=m;k++)
    {
        in>>i>>j>>cost;

        gf[i].push_back({cost,j});
        gf[j].push_back({cost,i});
    }

    int start=1;

    int nrComp=n;

    viz[start]=1;
    for(auto vec:gf[start])
        c.push( make_tuple(vec.Cost,vec.Nod,start) );

    while(nrComp!=1)
    {
        while( viz[ get<1>(c.top()) ] )
            c.pop();

        int cost,nod,nodAnt;
        tie(cost,nod,nodAnt)=c.top();
        c.pop();

        viz[nod]=1;

        for(auto vec:gf[nod])
            if(viz[ vec.Nod ]==0)
                c.push( make_tuple(vec.Cost,vec.Nod,nod) );

        if(nod!=nodAnt)
        {
            sol.push_back({nod,nodAnt});
            costTot+=cost;
            nrComp--;
        }
    }

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

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

    return 0;
}