#include <fstream>
#include <vector>
#include <algorithm>
#define f first
#define s second
const int NMAX=200055;

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

struct edge
{
    int a, b, c;
    bool operator<(const edge& other) const
    {
        return c<other.c;
    }
};

vector <edge> mm;
vector <pair<int, int>> ans;
int n, m, t[NMAX], sz[NMAX];

int find(int);
bool un(int, int);
void apm();

int main()
{
    int i, a, b, c;
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        t[i]=i;
        sz[i]=1;
    }
    for(i=1; i<=m; i++)
    {
        cin>>a>>b>>c;
        mm.push_back({a, b, c});
    }
    apm();
    return 0;
}

int find(int nod)
{
    if(t[nod]==nod) return nod;
    t[nod]=find(t[nod]);
    return t[nod];
}

bool un(int a, int b)
{
    a=find(a); b=find(b);
    if(a==b) return false;
    if(sz[a]>sz[b]) swap(a, b);
    t[a]=b;
    sz[b]+=sz[a];
    return true;
}

void apm()
{
    int cost=0;
    sort(mm.begin(), mm.end());
    for(auto i:mm)
    {
        if(un(i.a, i.b))
        {
            cost+=i.c;
            ans.push_back({i.a, i.b});
        }
    }
    cout<<cost<<'\n';
    cout<<ans.size()<<'\n';
    for(auto i:ans) cout<<i.f<<' '<<i.s<<'\n';
}