#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstdlib>

#define ll long long
#define pb push_back

using namespace std;

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

const int N = 2e5+10;
const int M = 4e5+10;

struct edges
{
    ll x, y, l;
};

int n, m;
edges x[N];

int par[N];
int rang[N];
bool b[N];

int compare(const void* a, const void* b)
{
    edges x1 = *(edges*)a;
    edges x2 = *(edges*)b;

    return x1.l - x2.l;
}

int findparent(int node)
{
    if(par[node] == node)
        return node;

    par[node] = findparent(par[node]);
    return par[node];
}

bool join(int x, int y)
{
    int px = findparent(x);
    int py = findparent(y);

    if(px == py)
        return 0;

    if(rang[px] > rang[py])
    {
        rang[py] += rang[px];
        par[px] = py;
    }
    else
    {
        rang[px] += rang[py];
        par[py] = px;
    }

    return 1;
}

int main()
{
    fin >> n >> m;

    for(int i = 0; i <= n; ++i)
    {
        par[i] = i;
        rang[i] = 1;
    }

    for(int i = 0; i < m; ++i)
        fin >> x[i].x >> x[i].y >> x[i].l;

    qsort(x, m, sizeof(edges), compare);

    int nr = 0;
    ll mst = 0;

    for(int i = 0; i <= m && nr < n; ++i)
    {
        b[i] = join(x[i].x, x[i].y);


        nr += b[i];
        mst += b[i] * x[i].l;
    }

    fout << mst << "\n";
    fout << n - 1 << "\n";

    nr = 0;
    for(int i = 0; i <= m && nr < n; ++i)
    {
        if(b[i])
        {
            fout << x[i].x << " " << x[i].y << "\n";
            ++nr;
        }
    }



    return 0;
}