#include <fstream>
#include <vector>

using namespace std;

struct edge
{
    int d;
    int w;
};

void Read(vector<edge> G[]);
void PRIM(vector<edge> G[]);
void minim(vector<edge> G[], int prezent[]);


ofstream g("apm.out");

int N,M,cost(0);

int main()
{
   vector<edge> G[200];
    Read(G);

   PRIM(G);
}


void Read(vector<edge> G[])
{
    ifstream f("apm.in");
    int n1,n2,c;
    edge temp;

    f >> N >> M;

    for (int i = 0; i<M; i++)
    {
        f >> n1 >> n2 >> c;
        temp.d = n2;
        temp.w = c;
        G[n1].push_back(temp);
        temp.d = n1;
        G[n2].push_back(temp);
    }
}

void PRIM(vector<edge> G[])
{
    int prezent[N+1];

    for (int i = 1; i<=N; i++)
        prezent[i] = -1;

    int k = 1;

    prezent[1] = 0;

    while (k != N)
    {
        minim(G,prezent);
        k++;
    }

    g << cost << endl << N-1;
    for (int i = 2; i<=N; i++)
    {
        g << endl;
        g <<i <<" "<< prezent[i];
    }

}

void minim(vector<edge> G[], int prezent[])
{
    int distMin = INT_MAX;
    int vert, su;

    for (int i = 1; i<=N; i++)
    {
        if(prezent[i]!=-1)
        {
            for (edge e : G[i])
            {
                if(prezent[e.d]==-1)
                    if(e.w < distMin)
                {
                    distMin = e.w;
                    vert = e.d;
                    su = i;
                }
            }
        }
    }


    prezent[vert]=su;
    cost += distMin;
}