#include <fstream>
#include<queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int lim=400005;
int n,m,i,tati[lim],rang[lim],cost_total,nr;
struct muchie
{
int a,b,cost;
}v[lim];
pair<int,int>legatura[lim];
struct cmp
{
    bool operator()(int x,int y)
    {
        return v[x].cost>v[y].cost;
    }
};
priority_queue<int,vector<int>,cmp>q;
int gasit(int nod)
{
    while(nod!=tati[nod])
        nod=tati[nod];
    return nod;
}
void adaugare(int x,int y)
{
    if(rang[x]<rang[y])
        tati[x]=y;
    if(rang[x]>rang[y])
        tati[y]=x;
    if(rang[x]==rang[y])
    {
        tati[x]=y;
        rang[y]++;
    }
}
void kruskal()
{
    while(!q.empty())
    {
        int x=gasit(v[q.top()].a);
        int y=gasit(v[q.top()].b);
        if(x!=y)
        {
            adaugare(x,y);
            cost_total+=v[q.top()].cost;
            legatura[++nr]=make_pair(v[q.top()].a,v[q.top()].b);
        }
        q.pop();
    }
}
int main()
{f>>n>>m;
    for(i=1;i<=m;i++)
{
    f>>v[i].a>>v[i].b>>v[i].cost;
    q.push(i);
}
for(i=1;i<=n;i++)
{
    tati[i]=i;
    rang[i]=1;
}
kruskal();
g<<cost_total<<"\n"<<n-1<<"\n";
for(i=1;i<=nr;i++)
    g<<legatura[i].first<<" "<<legatura[i].second<<"\n";

    return 0;
}