#include <iostream>
#include <bits/stdc++.h>
using namespace std;

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

int t[200002];
vector<int> v[200002];
bool viz[200002];
int n,m;
int nrmuc;
int x,y,cost;

int sef(int x)
{
    if(x != t[x])
        t[x] = sef(t[x]);
    return t[x];
}

void join(int x,int y)
{
    int t1 = sef(x);
    int t2 = sef(y);
    t[t2]=t1;
}

struct apm
{
    int n1,n2,c;
};

apm cit[400001];

bool cmp(apm a,apm b)
{
    if(a.c < b.c)
        return 1;
    return 0;
}

int main()
{
    in>>n>>m;
    for(int i = 1; i<=n; i++)
    {
        t[i]=i;
    }
    for(int i = 1; i<=m; i++)
    {
        in>>x>>y>>cost;
        cit[i].n1 = x;
        cit[i].n2 = y;
        cit[i].c = cost;
    }
    sort(cit + 1,cit + m + 1,cmp);
    int i = 1;
    cost = 0;
    while(nrmuc != n - 1)
    {
        int n1, n2;
        n1 = cit[i].n1;
        n2 = cit[i].n2;
        if(sef(n1) != sef(n2))
        {
            ++nrmuc;
            join(n1,n2);
            v[n1].push_back(n2);
            v[n2].push_back(n1);
            cost += cit[i].c;
        }
        ++i;
    }
    out<<cost<<"\n"<<n - 1<<"\n";
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j<v[i].size(); j++)
            if(i<v[i][j])
                out<<i<<" "<<v[i][j]<<"\n";

    }
    return 0;

}