#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
struct graf
{
    int x,y,cost;
};
int const nmax=400001;
graf a[nmax];
int sz[nmax],M[nmax];
vector <int> V[nmax];
bool comp(graf x, graf y)
{
    return x.cost<y.cost;
}

void Read()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        fin>>a[i].x>>a[i].y>>a[i].cost;
    }
    sort(&a[1],& a[m+1],comp);
    /*for(int i=1;i<=m;++i)
    {
        fout<<a[i].x<<" "<<a[i].y<<" "<<a[i].cost<<"\n";
    }*/
    for(int i=1; i<=n; ++i)
    {
        M[i]=i;
        sz[i]=1;
    }
}
int Find(int x)
{
    int root=x;
    int aux;
    while(M[root]!=root)root=M[root];
    while(M[x]!=root)
    {
        aux=M[x];
        M[x]=root;
        x=aux;
    }
    return root;
}
void Union(int x,int y)
{
    int root_x=Find(x);
    int root_y=Find(y);
    if(sz[root_x]<sz[root_y])
    {
        sz[root_y]+=sz[root_x];
        M[root_x]=root_y;
    }
    else
    {
        sz[root_x]+=sz[root_y];
        M[root_y]=root_x;
    }
}
void Solve()
{
    int nr=0,k=1,Cost=0;
    while(nr<n-1)
    {
        if(Find(a[k].x)!=Find(a[k].y))
        {
            Union(a[k].x,a[k].y);
            V[a[k].x].push_back(a[k].y);

            Cost+=a[k].cost;
            nr++;
        }
        k++;
    }
    fout<<Cost<<"\n";
    fout<<nr<<"\n";
    for(int i=1;i<=n;++i)
    {
        if(V[i].size())
        {
            for(int j=0;j<V[i].size();++j)
                fout<<i<<" "<<V[i][j]<<"\n";
        }
    }

}
int main()
{
    Read();
    Solve();
    return 0;
}