#include <bits/stdc++.h>

using namespace std;

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

int n, m, i, totalCost=0;

int main()
{

    f>>n>>m;
    set <pair<int, pair<int, int> > >edges;
    vector<bool>visited(n+1, false);
    vector<pair<int, int>>solution(n);

    for(i=1; i<=m; i++){

        int x, y, z;
        f>>x>>y>>z;

        edges.insert(make_pair(z, make_pair(x, y)));

    }

    i = 1;

    while(i<=n-1){

        pair < int, pair<int, int> >aux = *(edges.begin());
        edges.erase(edges.begin());

        int source =aux.second.first;
        int destination = aux.second.second;

        if(!(visited[source]==true && visited[destination]==true)){

            visited[destination] = true;
            visited[source]==true;

            solution[i] = make_pair(source, destination);

            totalCost += aux.first;
            i++;

        }

    }

    g<<totalCost<<'\n'<<n-1<<'\n';

    for(int j=1; j<i; j++)
        g<<solution[j].first<<' '<<solution[j].second<<'\n';

    return 0;
}