#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;
    vector< int > node_set;
    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));
    }
    f.close();

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

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

        if(node_set[a]!=node_set[b])
        {
                j=node_set[a];
                k=node_set[b];

            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);
                    node_set[*it]=j;
                }
        }
    }
/*
    cout<<"\n\nMultimi: \n";
    for(i=1;i<nodes.size();i++)
    {
        for(set<int>:: iterator it=nodes[i].begin(); it != nodes[i].end(); it++)
            cout<<*it<<" ";
        cout<<'\n';
    }
    */

    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;
}