///Algoritmul lui Kruskal
#include <fstream>
#include <algorithm>
#include <vector>
#define In "apm.in"
#define Out "apm.out"
#define Nmax 200002
#define Mmax 400002
using namespace std;
struct muchie
{
    int x,y,c;
    bool operator <(const muchie&A)const
    {
        return c<A.c;
    }
};
muchie a[Mmax],sol[Mmax];
int n,m,nr,sum,tata[Nmax];
vector< int >g[Nmax];
inline void Citire()
{
    int i;
    ifstream f(In);
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>a[i].x>>a[i].y>>a[i].c;
    f.close();
    sort(a+1,a+m+1);
}
inline void Init()
{
    int i;
    for(i=1;i<=n;i++)
    {
        tata[i] = i;
        g[i].push_back(i);
    }
}
//uneste componenta conexa a de componenta conexa b
inline void Uneste(int a,int b)
{
    for(vector<int>::iterator it=g[a].begin();it!=g[a].end();it++)
    {
        tata[*it] = b;
        g[b].push_back(*it);
    }
    g[a].clear();
}
inline void Rezolvare()
{
    muchie M;
    int i;
    for(i=1;i<=m;i++)
    {
        M = a[i];
        if(tata[M.x]!=tata[M.y])
        {
            if(g[tata[M.x]].size()<g[tata[M.y]].size())
                Uneste(tata[M.x],tata[M.y]);
            else
                Uneste(tata[M.y],tata[M.x]);
            sol[++nr] = M;
            sum+=M.c;
        }
    }
}
inline void Afisare()
{
    ofstream g(Out);
    g<<sum<<"\n"<<nr<<"\n";
    for(int i=1;i<=nr;i++)
        g<<sol[i].x<<" "<<sol[i].y<<"\n";
    g.close();
}
int main()
{
    Citire();
    Init();
    Rezolvare();
    Afisare();
    return 0;
}