#include <fstream>
#include <vector>
#include <iostream>
#include <list>
#include <algorithm>
#define INF (1<<30)-1
#define nmax 200001
#define mmax 400001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x,y,cost;
}m[mmax];
int n,nm,p[nmax],rang[nmax],len;
vector < pair <int,int> > sol;
int rad(int x)
{
    while(x!=p[x])
        x=p[x];
    return x;
}
void unite(int a, int b)
{
    if(rang[a]==rang[b])
    {
        rang[a]++;
        p[b]=a;
    }
    else if(rang[a]<rang[b]) p[a]=b;
            else p[b]=a;
}
bool compare(muchie a, muchie b)
{
    return (a.cost<b.cost);
}
int main()
{
    f>>n>>nm;
    int a,b,i,j,c;
    for(i=1;i<=nm;i++)
        f>>m[i].x>>m[i].y>>m[i].cost;

    for(i=1;i<=n;i++) p[i]=i;
    sort(m+1,m+nm+1,compare);

    for(i=1;i<=nm;i++)
    {
        a=rad(m[i].x);
        b=rad(m[i].y);
        if(a!=b)
        {
            sol.push_back(make_pair(m[i].x,m[i].y));
            len+=m[i].cost;
            unite(a,b);
        }
    }
    g<<len<<'\n';
    g<<n-1<<'\n';
    for(i=0;i<sol.size();i++)
        g<<sol[i].first<<' '<<sol[i].second<<'\n';
}