#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("A.in");
ofstream g("A.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;

struct muchie{
    int x,y,z;
};

void Union(int x,int y,vector < int >& h,vector < int >& T) //regula de ponderare
{
    if(h[x]<h[y]) T[x]=y;
    else
    {
        if(h[x]==h[y]) h[x]++;
        T[y]=x;
    }
}

int Find(int x,vector < int >& T) //compresie
{
    int root=x;
    while(T[root]!=-1)
        root=T[root];

    int aux=x;
    while(x!=root)
    {
        int aux=x;
        x=T[x];
        T[aux]=root;
    }

    return root;
}

int main()
{
    ifstream f("amp.in");
    ofstream g("amp.out");
    int V,E,a,b,c;
    f>>V>>E;
    vector < muchie > edges;
    vector < int > h(V,0),T(V,-1);
    for(int i=1;i<=E;i++)
    {
        f>>a>>b>>c;
        edges.pb({a,b,c});
    }
    sort(edges.begin(),edges.end(),[](muchie X,muchie Y){
       if(X.z==Y.z)
           return(X.x<Y.x);
       return(X.z<Y.z);
    });

    ll ans=0;
    vector < pi > rez;
    for(muchie el:edges)
    {
        int root_x=Find(el.x,T);
        int root_y=Find(el.y,T);

        if(root_x!=root_y) {
            rez.pb({el.x,el.y});
            ans+=el.z;
            Union(root_x, root_y, h, T);
        }
    }
    sort(rez.begin(),rez.end(),[](pi X,pi Y)
    {
       if(X.first==Y.first)
           return (X.second<Y.second);
       return (X.first<Y.first);
    });

    g<<ans<<'\n';
    g<<V-1<<'\n';
    for(pi el:rez) g<<el.first<<' '<<el.second<<'\n';

    return 0;
}