#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define NMax 200005

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

int n,m;
int tata[NMax];
int sum;

struct muchie
{
    int a,b,c;

    bool operator < (const muchie &t) const
    {
        if(c < t.c) return true;
        return false;
    }

} v[NMax];

vector < pair < int, int > > sol;

void update(int x,int y)
{
    if(x > y) swap(x,y);
    tata[y] = x;
}

int query(int x)
{
    if(tata[x] == x) return x;
    return tata[x] = query(tata[x]);
}

int main()
{
    int i;

    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>v[i].a>>v[i].b>>v[i].c;
    }

    sort(v+1,v+m+1);

    for(i=1;i<=n;++i) tata[i] = i;

    int q1,q2;
    for(i=1;i<=m;++i)
    {
        q1 = query(v[i].a);
        q2 = query(v[i].b);

        if(q1 != q2)
        {
            sum += v[i].c;
            sol.push_back(make_pair(v[i].a,v[i].b));
            update(q1,q2);
        }
    }

    g<<sum<<"\n"<<sol.size()<<"\n";
    for(i=0;i<sol.size();++i) g<<sol[i].first<<" "<<sol[i].second<<"\n";

    f.close();
    g.close();
    return 0;
}