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

using namespace std;

int viz[200005];
priority_queue <tuple<int,int,int> > myheap;
vector <int> graph[200005];
vector <int> graphc[200005];
vector <pair<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();
    viz[start]=1;
    int nr_muchii_finale=0;
    for(i=0;i<lim;i++)
    {
        x=start;
        y=graph[x][i];
        c=graphc[x][i];
        myheap.push(make_tuple(-c,x,y));
    }
    while(nr_muchii_finale!=N-1)
    {
        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)
        {
            muchii_finale.push_back(make_pair(get<1>(muchie),get<2>(muchie)));
            cost_total=cost_total+c;
            if(viz[y]==0)
            {
                nr_muchii_finale++;
                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)
            {
                nr_muchii_finale++;
                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,lim;
    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;
    lim=muchii_finale.size();
    g<<lim<<endl;
    for(i=0;i<lim;i++)
    {
        //g<<get<1>(muchii_finale[i])<<" "<<get<2>(muchii_finale[i])<<endl;
        g<<muchii_finale[i].first<<" "<<muchii_finale[i].second<<endl;
    }
    return 0;
}