#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <bitset>
#define MAX 200021

using namespace std;

ifstream f("apm.in");
ofstream out("apm.out");

vector < pair < int , int > > v[MAX];
vector < pair < int , pair < int , int > > > g, rez;

bitset < MAX > viz;

int n, m, T[MAX];

void read()
    {
        int x, y, cst;
        f>>n>>m;
        for(int i=1; i<=m; i++)
        {
            f>>x>>y>>cst;
            v[x].push_back({y, cst});
            v[y].push_back({x, cst});
            g.push_back({cst, {x, y}});
        }
    }

int parent(int x)
    {
        if(T[x]==x)
            return x;
        return T[x] = parent(T[x]);
    }

int main()
{
    long long int sum=0;
    read();
    for(int i=1; i<=n; i++)
        T[i]=i;
    sort(g.begin(), g.end());
    /*for(auto it : g)
        cout<<it.second.first<<" "<<it.second.second<<" "<<it.first<<endl;*/
    for(auto it : g)
    {
        int x = parent(it.second.first);
        int y = parent(it.second.second);
        if(x!=y)
        {
            rez.push_back({it.first , {x, y}});
            T[x] = y;
            sum+=it.first;
        }
    }
    out<<sum<<'\n';
    out<<n-1<<'\n';
    for(auto it : rez)
        out<<it.second.first<<" "<<it.second.second<<'\n';

}