#include <bits/stdc++.h>
using namespace std;
#define inf 1e9
ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX = 2 * 1e5;
int g[NMAX + 5][NMAX + 5];
int d[NMAX + 5];
bool viz[NMAX + 5];
int tata[NMAX + 5];
int n, m;

void prim()
{
    for(int i = 1; i <= n; ++i)
    {
        d[i] = g[1][i];
        tata[i] = 1;
    }
    d[0] = inf;
    tata[1] = 0;
    viz[1] = 1;

    for(int k = 1; k < n; ++k)
    {
        int best_nod = 0;

        for(int j = 1; j <= n; ++j)
        {
            if(!viz[j] && d[j] < d[best_nod])
            {
                best_nod = j;
            }
        }

        if(best_nod >= 1)
        {
            viz[best_nod] = 1;
            for(int k = 1; k <= n; ++k)
            {
                if(!viz[k] && d[k] > g[best_nod][k])
                {
                    d[k] = g[best_nod][k];
                    tata[k] = best_nod;
                }
            }
        }
    }

    int cost = 0;

    for(int i = 1; i <= n; ++i)
    {
        cost += d[i];
    }

    out << cost << '\n';
    out << n - 1 << '\n';

    for(int i = 2; i <= n; ++i)
    {
        out << i << tata[i] << '\n';
    }
}

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

    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= i; ++j)
        {
            g[i][j] = g[j][i] = inf;
        }
        g[i][i] = 0;
    }

    for(int i = 1; i <= m; ++i)
    {
        int u, v, c;
        in >> u >> v >> c;
        g[u][v] = c;
        g[v][u] = c;
    }

    prim();
    return 0;
}