#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;
pair <int,int> tree[3*MAX_SIZE];


void update_tree(int nod , int left , int right ,int A , int B , int value)
{
    if (left == right)
    {
        tree[nod].first = value;
        tree[nod].second = A;
    }
    else
    {
        int middle  = (left + right) >> 1;
        int left_son = nod << 1;
        int right_son = left_son + 1;
        if (A <= middle)
        {
            update_tree(left_son , left , middle , A ,  B , value);
        }
        if ( middle < B)
        {
            update_tree(right_son , middle + 1 , right , A , B , value);
        }
        if ( tree[left_son].first > tree[right_son].first)
        {
            tree[nod] = tree[right_son];
        }
        else
        {
            tree[nod] = tree[left_son];
        }
    }
}

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;
        update_tree(1,1,N,nod,nod,10000000);
        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;
                update_tree(1,1,N,x,x,w[nod][i]);
            }
        }
        int minim = tree[1].first;
        nod = tree[1].second;
        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));
    memset(tree,1000000,sizeof(tree));
    APM(1);

    return 0;
}