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

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

struct ura
{
    int a,b,val;
}v[400001];

int r[200001];

bool cmp(ura A , ura B)
{
    return A.val < B.val;
}

int findd(int x)
{
    if (r[x] == x)
    {
        return x;
    }
    return r[x] = findd(r[x]);
}

void conectare(int x , int y)
{
    int rx = findd(x) , ry = findd(y);
    if (rx == ry)
    {
        return;
    }
    r[rx] = ry;
}

int rez1[400001];
int rez2[400001];
int main()
{
    int n,m;
    cin >>n>>m;
    for (int i = 1; i <= m; i++)
    {
        cin >>v[i].a>>v[i].b>>v[i].val;
    }
    for (int i = 1; i <= n; i++)
    {
        r[i] = i;
    }
    sort (v + 1 , v + m + 1 , cmp);
    int nr = n - 1;
    int sum = 0;
    int cnt = 0;
    for (int i = 1; i <= m && nr > 0; i++)
    {
        if (findd(v[i].a) != findd(v[i].b))
        {
            conectare(v[i].a , v[i].b);
            sum += v[i].val;
            nr--;
            cnt++;
            rez1[cnt] = v[i].a;
            rez2[cnt] = v[i].b;
        }
    }
    cout <<sum<<"\n"<<n - 1<<"\n";
    for (int i = 1; i <= cnt; i++)
    {
        cout <<rez1[i]<<" "<<rez2[i]<<"\n";
    }
    return 0;
}