#include <iostream>
#include <vector>
#include <utility>
#include <set>
#include <algorithm>
#include <fstream>
using namespace std;

bool comp(pair<int,int> a,pair<int,int> b)
{
    return a.first<b.first;
}

int main()
{
    vector< pair<int,int> > edges;
    vector< pair<int,int> > costs;
    vector< pair<int,int> > tree_edges;
    vector< set<int> > nodes;
    int n, m, i, j, k, a, b, c, cost=0;
    set<int> aux;
    ifstream f("apm.in");
    f>>n>>m;
    for(i=0;i<m;i++)
    {
        f>>a>>b>>c;
        edges.push_back(make_pair(a,b));
        costs.push_back(make_pair(c,i));
        aux.insert(a);
    }
    f.close();

    for(i=0;i<=n;i++)
    {
        aux.insert(i);
        nodes.push_back(aux);
        aux.clear();
    }

    sort(costs.begin(), costs.end(), comp);
    for(i=0;i<costs.size();i++)
    {
        c=costs[i].second;
        if(edges[c].first<edges[c].second)
        {   a=edges[c].first;
            b=edges[c].second;
        }
        else
        {   b=edges[c].first;
            a=edges[c].second;
        }

        for(j=1;j<nodes.size();j++)
            if(nodes[j].find(a)!= nodes[j].end())
                break;
        for(k=1;k<nodes.size();k++)
            if(nodes[k].find(b)!= nodes[k].end())
                break;
        if(j!=k)
        {
            tree_edges.push_back(edges[c]);
            cost = cost + costs[i].first;
            for(set<int>:: iterator it=nodes[k].begin(); it != nodes[k].end(); it++)
                nodes[j].insert(*it);
            nodes.erase(nodes.begin()+k);
        }
    }

    ofstream g("apm.out");
    g<<cost<<'\n'<<n-1<<'\n';
    for(i=0;i<tree_edges.size();i++)
        g<<tree_edges[i].first<<" "<<tree_edges[i].second<<'\n';
    g.close();
    return 0;
}