#include <fstream>
#include <vector>
#define INF 1000000000

using namespace std;

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

int n,m,i,j,d[200010],t[200010],f[200010];
int x,y,cost,minim,k,l,sol;
pair <int, int> s[200010];
vector< pair <int, int> > L[200010];

int main()
{
    fin >> n >> m;
    ///d[i] = distanta minima de la nodul i la unul dintre nodurile
    ///din apm deja format
    ///f[i] = 1 pentru nodurile deja puse in apm (contor)
    ///t[i] = acel nod din apm spre care este din nodul i
    ///distanta minima
    for (i=1; i<=m; i++)
    {
        fin >> x >> y >> cost;
        L[x].push_back(make_pair(y, cost));
        L[y].push_back(make_pair(x, cost));
    }
    for (i=1; i<=n; i++)
        d[i] = INF;
    d[1] = 0;
    for (i=1; i<=n; i++)
    {
        minim = INF;
        ///calculez min din d pentru cele nemarcate
        for (j=1; j<=n; j++)
            if (d[j] < minim && f[j] == 0)
            {
                minim = d[j];
                k = j;
            }
        ///nodul k este ales pentru a fi pus in apm
        ///punem muchia k, t[k]
        if (i != 1)
        {
            s[++l].first = k;
            s[l].second = t[k];
            sol += d[k];
            ///costul muchiei k, t[k]
        }
        f[k] = 1;
        for (j=0; j<L[k].size(); j++)
        {
            int vecin = L[k][j].first;
            int cost = L[k][j].second;
            if (f[vecin] == 0 && d[vecin] > cost)
            {
                d[vecin] = cost;
                t[vecin] = k;
            }
        }
    }
    fout << sol << "\n" << n-1 << "\n";
    for (i=1; i<n; i++)
        fout << s[i].first << " " << s[i].second << "\n";
    return 0;
}