#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int maxn=400005;
int n,m,i,a,b,c,s,COST,nods,nodd;
vector < pair < int , int > > x[maxn],sol;
bool viz[maxn];

struct cmp
{
    bool operator() (const pair< int , int > &p,const pair< int , int > &q)
    {
        return x[p.first][p.second].second > x[q.first][q.second].second;
    }
};
priority_queue < pair< int , int > , vector < pair< int, int> > , cmp > pq;

void read()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        x[a].push_back(make_pair(b,c));
        x[b].push_back(make_pair(a,c));
    }
}

void add_muchii( int nod )
{
    for(int i=0;i<x[nod].size();i++)
        if(viz[ x[nod][i].first ] == false)
            pq.push(make_pair(nod,i));
}

void prim(int nod)
{
    int s=n-1;
    while(s)
    {

        nods=pq.top().first;
        nodd=pq.top().second;
        while(viz[x[nods][nodd].first]==true)
        {
            pq.pop();
            nods=pq.top().first;
            nodd=pq.top().second;
        }

        pq.pop();
        COST += x[nods][nodd].second;

        viz[ x[nods][nodd].first ]=true;
        add_muchii( x[nods][nodd].first );
        sol.push_back(make_pair( nods , x[nods][nodd].first ));

        s--;
    }
}

void write()
{
    printf("%d\n%d\n",COST,sol.size());
    for(i=0;i<=n-2;i++)
        printf("%d %d\n",sol[i].first,sol[i].second);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    add_muchii(1);
    viz[1]=true;
    prim(1);
    write();
    return 0;
}