#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
#include <fstream>
#include <set>
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;
    set< int > nodes;
    edge ed;
    int n, m, v1, v2, i, cost=0;
    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();
    sort(edges.begin(), edges.end(), comp);
    nodes.insert(1);
    while(tree_edges.size()<n-1)
    {
        for(i=0;i<edges.size();i++)
           // if(nodes.find(edges[i].a)!=nodes.end() || nodes.find(edges[i].b)!=nodes.end())
           {
             v1 = nodes.find(edges[i].a)!=nodes.end() && nodes.find(edges[i].b)==nodes.end();
             v2 = nodes.find(edges[i].b)!=nodes.end() && nodes.find(edges[i].a)==nodes.end();
             if(v1 != 0)
               {
                   nodes.insert(edges[i].b);
                   tree_edges.push_back(edges[i]);
                   cost=cost+edges[i].c;
                   edges.erase(edges.begin()+i);
                   break;
               }
             if(v2 != 0)
                {
                   nodes.insert(edges[i].a);
                   tree_edges.push_back(edges[i]);
                   cost=cost+edges[i].c;
                   edges.erase(edges.begin()+i);
                   break;
               }
           }
    }
    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;
}