#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define edge pair< int, int >
#define MAX 1001

vector< pair< int, edge > > GRAPH, MST;

int parent[MAX], total, N, E;

int findset(int x, int *parent)
{
    if(x != parent[x])
        parent[x] = findset(parent[x], parent);
    return parent[x];
}

void kruskal()
{
    int i, pu, pv;
    sort(GRAPH.begin(), GRAPH.end());  
    for(i=total=0; i<E; i++)
    {
        pu = findset(GRAPH[i].second.first, parent);
        pv = findset(GRAPH[i].second.second, parent);
        if(pu != pv)
        {
            MST.push_back(GRAPH[i]);  
            total += GRAPH[i].first;  
            parent[pu] = parent[pv];  
        }
    }
}

void reset()
{
        for(int i=1; i<=N; i++) parent[i] = i;
}

void print(FILE *out)
{
    int i, sz ;
    // this is just style...
    sz = MST.size();
    fprintf (out , "%d \n%d\n" ,total ,sz) ;
    for(i=0; i<sz; i++)
    {
        fprintf(out, "%d ", MST[i].second.first);
        fprintf(out, "%d\n", MST[i].second.second);
    }
}

int main()
{
    int i, u, v, w;
    FILE *in , *out ;
    in=fopen("apm.in" , "r") ;
    out=fopen("apm.out" , "w") ;

    fscanf(in , "%d %d", &N, &E);
    reset();
    for(i=0; i<E; i++)
    {
        fscanf(in , "%d %d %d", &u, &v, &w);
        GRAPH.push_back(pair< int, edge >(w, edge(u, v)));
    }
    kruskal(); // runs kruskal and construct MST vector
    print(out); // prints MST edges and weights

    return 0;
}