#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string.h>
#define MAX_SIZE 200000
#define INF 1000000;
using namespace std;


vector <int> graf[MAX_SIZE];
vector <int> w[MAX_SIZE];
int N , M;
int cost[MAX_SIZE];
bool sel[MAX_SIZE];
int muchii[MAX_SIZE];
int total = 0;

void APM(int nod)
{
    ofstream output("apm.out");
    cost[nod] = INF;
    sel[nod] = true;
    int minim = INF;
    int next;
    int cost_total = 0;
    vector <int> sol;
    for (int k =0;k<N-1;k++)
    {
        sel[nod] = true;
        for (int i =0;i < graf[nod].size();i++)
        {
            int x = graf[nod][i];
            if ( cost[x] > w[nod][i]  && sel[x] == false)
            {
                cost[x] = w[nod][i];
                muchii[x] = nod;
            }
        }
        int minim = INF;
        for (int i = 1;i<=N;i++)
        {
            if (minim > cost[i] && sel[i] == false)
            {
                minim = cost[i];
                nod = i;
            }
        }

        cost_total += minim;
        sol.push_back(nod);
    }
    output << cost_total << "\n" << N -1 << "\n";
    for (int i =0;i<sol.size();i++)
    {
        int x = sol[i];
        output << muchii[x] << " " << x << "\n";
    }
}

void read_data()
{
    ifstream input("apm.in");
    input >> N >> M;
    for (int i =0;i<M;i++)
    {
        int x , y, c;
        input >> x >> y >> c;
        graf[x].push_back(y);
        graf[y].push_back(x);
        w[x].push_back(c);
        w[y].push_back(c);
    }
    input.close();
}


int main()
{
    read_data();
    memset(cost,1000000,sizeof(cost));
    APM(1);

    return 0;
}