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

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

using namespace std;

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

struct cmp{
bool operator () (pair <int,int> a,pair <int,int> b)
{
    return a.nd<b.nd;
}
};

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

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

int main()
{
    f>>n>>m;
    for(int i=0;i<n;++i)
        val[i]=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;
}