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

struct edge{int a;
            int b;
            int c;};

bool comp(edge e1, edge e2)
{
    return e1.c<e2.c;
}

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

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

    sort(edges.begin(), edges.end(), comp);
    for(i=0;i<edges.size() && tree_edges.size()<n-1;i++)
    {
        if(node_set[edges[i].a]!=node_set[edges[i].b])
        {
            j=node_set[edges[i].a];
            k=node_set[edges[i].b];
            if(j>k)
                swap(j,k);
            tree_edges.push_back(edges[i]);
            cost = cost + edges[i].c;
            for(set<int>:: iterator it=nodes[k].begin(); it != nodes[k].end(); it++)
                {
                    nodes[j].insert(*it);
                    node_set[*it]=j;
                }
        }
    }

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