#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <tuple>

using namespace std;
//int dist[200000];
//int tata[200000];
int viz[200005];
priority_queue <tuple<int,int,int> > myheap;
vector <int> graph[200005];
vector <int> graphc[200005];
vector <tuple<int,int,int> > muchii_finale;
int N,M;
int cost_total;
void prim(int start)
{
    int i,lim,x,y,c,cost,vecin;
    tuple <int,int,int> muchie;
    lim=graph[start].size();
    //cout<<lim<<endl;
    viz[start]=1;
    for(i=0;i<lim;i++)
    {
        x=start;
        y=graph[x][i];
        c=graphc[x][i];
        myheap.push(make_tuple(-c,x,y));
        //cout<<"muchie bagata in heap"<<endl;
    }
    while(myheap.empty()==0)
    {
        muchie=myheap.top();
        get<0>(muchie)=-get<0>(muchie);
        c=get<0>(muchie);
        x=get<1>(muchie);
        y=get<2>(muchie);
        myheap.pop();
        if(viz[x]==0 || viz[y]==0)
        {
            //cout<<"muchie buna"<<endl;
            muchii_finale.push_back(muchie);
            //cout<<get<0>(muchie)<<" "<<get<1>(muchie)<<" "<<get<2>(muchie)<<endl;
            cost_total=cost_total+c;
            if(viz[y]==0)
            {
                viz[y]=1;
                lim=graph[y].size();
                for(i=0;i<lim;i++)
                {
                    vecin=graph[y][i];
                    cost=graphc[y][i];
                    if(viz[vecin]==0)
                        myheap.push(make_tuple(-cost,y,vecin));
                }
            }
            if(viz[x]==0)
            {
                viz[x]=1;
                lim=graph[x].size();
                for(i=0;i<lim;i++)
                {
                    vecin=graph[x][i];
                    cost=graphc[x][i];
                    if(viz[vecin==0])
                        myheap.push(make_tuple(-cost,x,vecin));
                }
            }
        }
    }
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int x,y,c,i;
    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        graph[x].push_back(y);
        graph[y].push_back(x);
        graphc[x].push_back(c);
        graphc[y].push_back(c);
    }
    prim(1);
    g<<cost_total<<endl;
    g<<muchii_finale.size()<<endl;
    for(i=0;i<muchii_finale.size();i++)
    {
        g<<get<1>(muchii_finale[i])<<" "<<get<2>(muchii_finale[i])<<endl;
    }
    return 0;
}