#include <iostream>
#include <fstream>
#include <set>
#include <bitset>
#include <vector>
#define Nmax 200001
#define Cmax 100000

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m, cost, lungime;
int dist[Nmax]; ///dist[i]= distanta minima de la i la arbore
int muchie[Nmax]; ///muchie[i]=j <=> muchia i-j reprezinta muchia de nod minim de la i la arbore (j apartine arborelui)
int a[Nmax], nr; ///elem din arbore
vector <pair<int, int> > arbore; ///arborele proriu-zis
bitset <Nmax> used; ///verifica dace elem i este sau nu in arbore
vector<pair<int,int> > gr[Nmax];
set <int> Q;

void actualizare(int x)
{
    for(auto i:gr[x])
    {
        if(dist[i.first]>i.second)
        {
            dist[i.first]=i.second;
            muchie[i.first]=x;
        }
    }
}
int minimum()
{
    int x=Cmax, l=-1;
    for(int i=1;i<=n;i++)
    {
        if(used[i]==0 && x>dist[i])
        {
            x=dist[i];
            l=i;
        }
    }
    return l;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        gr[x].push_back(make_pair(y,z));
        gr[y].push_back(make_pair(x,z));
    }
    for(int i=1;i<=n;i++)
    {
        dist[i]=Cmax;
        muchie[i]=-1;
        Q.insert(i);
    }
    a[++nr]=*Q.begin();
    Q.erase(Q.begin());
    actualizare(a[nr]);
    used[a[nr]]=1;
    while(!Q.empty())
    {
        int k=minimum();
        a[++nr]=k;
        used[k]=1;
        Q.erase(Q.find(k));
        if(muchie[k]!=-1){
            arbore.push_back(make_pair(muchie[k], k));
            lungime++;
            cost+=dist[k];
        }
        actualizare(k);
    }
    g<<cost<<'\n'<<lungime<<'\n';
    for(unsigned int i=0;i<arbore.size();i++)
    {
        g<<arbore[i].first<<" "<<arbore[i].second<<'\n';
    }
    return 0;
}