#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 <pair<int, int>> Q; /// pair: dist minima + nod
void actualizare(int x)
{
    for(unsigned int i=0;i<gr[x].size();i++)
    {
        if(used[gr[x][i].first]==1)
            gr[x].erase(gr[x].begin()+i);
        else if(dist[gr[x][i].first]>gr[x][i].second && used[gr[x][i].first]==0)
        {
            Q.erase(Q.find(make_pair(dist[gr[x][i].first], gr[x][i].first)));
            Q.insert(make_pair(gr[x][i].second, gr[x][i].first));
            dist[gr[x][i].first]=gr[x][i].second;
            muchie[gr[x][i].first]=x;
        }
    }
}
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(make_pair(Cmax, i));
    }
    pair <int, int> fr=*Q.begin();
    a[++nr]=fr.second;
    Q.erase(Q.begin());
    actualizare(a[nr]);
    used[a[nr]]=1;
    while(!Q.empty())
    {
        pair <int, int> fr=*Q.begin();
        a[++nr]=fr.second;
        used[a[nr]]=1;
        Q.erase(Q.begin());
        if(muchie[a[nr]]!=-1){
            arbore.push_back(make_pair(muchie[a[nr]], a[nr]));
            lungime++;
            cost+=dist[a[nr]];
        }
        actualizare(a[nr]);
    }
    g<<cost<<'\n'<<lungime<<'\n';
    for(unsigned int i=0;i<arbore.size();i++)
    {
        g<<arbore[i].first<<" "<<arbore[i].second<<'\n';
    }
    return 0;
}