#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <set>
#include <stack>

#define NMAX 200000
#define st first
#define nd second

using namespace std;

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

vector < pair <int,int>> v[NMAX],rez;
int n,m,viz[NMAX],val[NMAX][2];

int APM()
{
    int ans=0,m,e=0,e1;
    val[0][0]=0;
    for(int i=0;i<n;++i)
    {
        viz[e]=1;
        ans+=val[e][0];
        m=1e9;
        for(auto x:v[e])
            if(!viz[x.st])
        {
            if(x.nd<val[x.st][0])
                {val[x.st][0]=x.nd;
                val[x.st][1]=e;}
        }
        for(int j=0;j<n;++j)
            if(!viz[j] && val[j][0]<m)
                m=val[j][0],e=j,e1=val[j][1];
        rez.push_back(make_pair(e,e1));
    }
    return ans;
}

int main()
{
    f>>n>>m;
    for(int i=0;i<n;++i)
        val[i][0]=1e9;
    while(m--)
    {
        int x,y,z;
        f>>x>>y>>z;
        v[x-1].push_back(make_pair(y-1,z));
        v[y-1].push_back(make_pair(x-1,z));
    }
    g<<APM()<<'\n';
    rez.pop_back();
    g<<rez.size()<<'\n';
    for(auto x:rez)
        g<<x.st+1<<' '<<x.nd+1<<'\n';

    return 0;
}