#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 200020

int N,M;
int APM_Cost;
int Father[NMAX];
int MaxDepth[NMAX];

struct Knoten
{
    int edge1,edge2,cost;

    Knoten()
    {

    }

    Knoten(int a, int b, int c)
    {
        edge1 = a;
        edge2 = b;
        cost = c;
    }

    bool operator() (Knoten i, Knoten j)
    {
        return i.cost<j.cost;
    }
};

vector < unsigned > APM;
vector < Knoten > Vertices;

int Root(int n)
{
    if(n == Father[n])
        return n;

    Father[n] = Root(Father[n]);
    return Father[n];
}

void Join(int a, int b)
{
    int rootA = Root(a);
    int rootB = Root(b);

    if(MaxDepth[rootA] > MaxDepth[rootB])
        Father[rootB] = rootA;
    else
        Father[rootA] = rootB;

    if(MaxDepth[rootA] == MaxDepth[rootB])
        MaxDepth[rootB]++;
}

inline bool AreBrothers(int a, int b)
{
    return Root(a)==Root(b);
}

void Read()
{
    freopen("apm.in","r",stdin);
    scanf("%d%d",&N,&M);
    for(int i=1,x,y,z;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        Vertices.push_back(Knoten(x,y,z));
    }
}

void Solve_Kruskal()
{
    Knoten cmp;
    sort(Vertices.begin(),Vertices.end(),cmp);

    for(int i=1;i<=N;Father[i]=i,i++);

    for(unsigned i=0; i<M && APM.size()<N-1;i++)
    {
        if(AreBrothers(Vertices[i].edge1,Vertices[i].edge2))
            continue;
        Join(Vertices[i].edge1,Vertices[i].edge2);
        APM_Cost += Vertices[i].cost;
        APM.push_back(i);
    }
}

void Print()
{
    freopen("apm.out","w",stdout);

    printf("%d\n%u\n",APM_Cost,N-1);

    for(vector < unsigned > :: iterator it = APM.begin(); it!=APM.end(); ++it)
        printf("%u %u\n",Vertices[*it].edge1,Vertices[*it].edge2);
}

int main()
{
    Read();
    Solve_Kruskal();
    Print();
    return 0;
}