#include <bits/stdc++.h>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n,m,p[400010],sum;
struct muc
{
    int cost,a,b;

}muchii[400010];
bool cmp(muc i,muc j)
{
    return (i.cost<j.cost);
}

int parent(int x)
{
    if(p[x]==x) return x;
    p[x]=parent(p[x]);
    return p[x];
}
int main()
{
    int x,y,c;
    in>>n>>m;
    for(int i=1;i<=m;i++)p[i]=i;
    for(int i=0;i<m;i++)
    {
        in>>muchii[i].a>>muchii[i].b>>muchii[i].cost;
    }
    sort(muchii,muchii+m,cmp);
    //cout<<5;
    int i=0,j=1;
    vector <muc> arbore;
    while(i<n-1)
    {
        x=muchii[i].a;
        y=muchii[i].b;
        int A=parent(x);
        int B=parent(y);
        if(A!=B)
        {
            p[A]=B;
            sum+=muchii[i].cost;
            arbore.push_back(muchii[i]);
        }
        i++;

    }
    out<<sum<<'\n'<<n-1<<'\n';
    for(int i=0;i<arbore.size();i++)
        out<<arbore[i].a<<' '<<arbore[i].b<<'\n';

    return 0;
}