/*#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;
}
*/
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxm=400005,maxn=200005;
struct oaie
{
    int st,dr,cost;
};
int n,m,i,COST,tt[maxn],t1,t2,rang[maxn];
oaie muc[maxm];
vector <int> sol;

void read()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&muc[i].st,&muc[i].dr,&muc[i].cost);
}

bool cmp(oaie a,oaie b)
{
    return a.cost<b.cost;
}

void write()
{
    printf("%d\n%d\n",COST,sol.size());
    for(i=0;i<sol.size();i++)
        printf("%d %d\n",muc[sol[i]].st,muc[sol[i]].dr);
}

int tata(int i)
{
    if(tt[i]==i)  return i;
    else
        i=tata(tt[i]);
    return i;
}

void unire(int i,int j)
{
    if(rang[i]<rang[j])
        tt[i]=j;
    else
    {
        tt[j]=i;
        if(rang[i]==rang[j])
            rang[i]++;
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    sort(muc+1,muc+m+1,cmp);

    int nrrep=n;
    for( i=1 ; i<=n ; tt[i]=i , i++ );
    i=1;
    while(nrrep>1)
    {
        t1=tata(muc[i].st);
        t2=tata(muc[i].dr);
        if(t1!=t2)
        {
            COST+=muc[i].cost;
            nrrep--;
            unire(t1,t2);
            sol.push_back(i);
        }
        i++;
    }

    write();
    return 0;
}