#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int MMax=400005;
const int NMax=200005;
const int oo=(1<<30);
int N,M;
int x[MMax],y[MMax],c[MMax],cost;
bitset<NMax> used;

struct compara
{
    bool operator()(int x , int y)
    {
        return c[x]>c[y];
    }
};



vector<int> g[NMax];
vector<int> apm;
priority_queue < int,vector < int >,compara> coada;

void citeste()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>x[i]>>y[i]>>c[i];
        g[x[i]].push_back(i);
        g[y[i]].push_back(i);
    }
}

void prim()
{
    used[1]=1;
    for(auto it:g[1])
        coada.push(it);
    for(int cnt=N-1;cnt;cnt--)
    {
        int i;
        do
        {
            i=coada.top();coada.pop();
        }
        while(used[x[i]]&&used[y[i]]);
        cost+=c[i];
        apm.push_back(i);
        i=used[y[i]]?x[i]:y[i];
        used[i]=1;
        for(auto it:g[i])
            coada.push(it);
    }
}

void afiseaza()
{
    fout<<cost<<'\n';
    fout<<N-1<<'\n';
    for(auto it:apm)
        fout<<x[it]<<' '<<y[it]<<'\n';
}


int main()
{
    citeste();
    prim();
    afiseaza();
    return 0;
}