#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

vector< vector < pair <int, int> > > G;  //(x,y,-c)
priority_queue< pair <int, pair <int, int> > > myheap;//max-heap   (-c,x,y)
vector <int> viz;
queue <pair <int, int> > afis;
int N, M;
int cost_total=0;

void Prim(int nod_start)
{
    vector< pair< int, int> >:: iterator i;
    for(i=G[nod_start].begin();i!=G[nod_start].end();i++)
        myheap.push(make_pair(i->second,make_pair(nod_start,i->first)));
    viz[nod_start]=1;
    pair<int, pair<int,int> > nod;
    while(!myheap.empty())
    {
        nod=myheap.top();
        myheap.pop();
        int x,y,cost;
        cost=-nod.first;
        x=nod.second.first;
        y=nod.second.second;
        if(viz[x]+viz[y]!=1)
            continue;
        cost_total+=cost;
        afis.push(make_pair(x,y));
        if(viz[x]==0)
            y=x;
        viz[y]=1;
        for(i=G[y].begin();i!=G[y].end();i++)
            if(viz[y]+viz[i->first]==1)///NU uita conditia astaaa
                myheap.push(make_pair(i->second, make_pair(y,i->first)));
    }
}

int main()
{
    fin>>N>>M;
    G.resize(N+1);// nod ul de start va fi 1 la mine
    viz.resize(N+1,0);
    ///CITIRE
    for(int i=1;i<=M;i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        G[x].push_back(make_pair(y,-cost));
        G[y].push_back(make_pair(x,-cost));
    }
    Prim(1);
    ///AFISARE
    fout<<cost_total<<endl<<N-1<<endl;
    pair <int, int> pereche;
    while(afis.empty()==0)
    {
        pereche=afis.front();
        afis.pop();
        fout<<pereche.first<<" "<<pereche.second<<" "<<endl;
    }
     return 0;


}