#include <bits/stdc++.h>
#define st first
#define nd second
#define NMAX 200001
#define pb push_back
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int nrm, n, m, i, j, x, y, tata[NMAX], h[NMAX], cost;
struct Muchie
{
    int x, y;
    double cost;
    friend bool operator > (const Muchie&, const Muchie&);
};
bool operator > (const Muchie& m1, const Muchie& m2)
{
    return m1.cost>m2.cost;
}
priority_queue <Muchie,vector<Muchie>, greater <Muchie> > pq;
vector < pair<int,int> > sol;
int Find(int x)
{
    int y=x;
    while(tata[y])
        y=tata[y];
    x=y;
    while(tata[x])
    {
        int r=tata[x];
        tata[x]=y;
        x=r;
    }
    return y;
}
void Union(int x, int y)
{
    x=Find(x), y=Find(y);
    if(h[x]>h[y])
            tata[y]=x;
    else if(h[x]<h[y])
        tata[x]=y;
    else
    {
        tata[y]=x;
        h[x]++;
    }
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        Muchie a;
        fin>>a.x>>a.y>>a.cost;
        pq.push(a);
    }
    while(sol.size()<n-1)
    {
        Muchie a=pq.top();
        pq.pop();
        if(Find(a.x)==Find(a.y))
            continue;
        Union(a.x,a.y);
        sol.pb({a.x,a.y});
        cost+=a.cost;
        nrm++;
    }
    fout<<cost<<'\n'<<sol.size()<<'\n';
    for(i=0;i<sol.size();++i)
        fout<<sol[i].st<<' '<<sol[i].nd<<'\n';
    return 0;
}