#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include<cstdio>
#include<set>
using namespace std;
ifstream f("apm.in");
ofstream g1("apm.out");
int w,m,q,fn;      //m = nr muchii, fn = nr finale
struct muchie
{
    int in,out,cost;
    bool operator <(const muchie& pt) const
    {
        return cost<=pt.cost;
    }
};

//vector <muchie> Q[100];
//set <muchie> v;
vector<muchie> v;
bool sortcomp(muchie i,muchie j)
{
    return i.cost<j.cost;
}
void citire()
{
    muchie nou;
    int i,j,n,y,c;
    
    f>>n;
    f>>m;
    for(i=1; i<=m; i++)
    {
        f>>j>>y>>c;
        
        nou.in=j;
        nou.out=y;
        nou.cost=c;
        v.push_back(nou);
        //Q[j].push_back(nou);
    }
}
int find(int *v,int n)
{
    int k=n;
    while(v[k]!=-1)
    {
        if(v[k]!=-1) k=v[k];
    }
    return k;
    
}
int main()
{
    int i,l=0;
    int cs = 0,k=0;
    citire();
    int *g=new int(m+10);
    muchie *x=new muchie[m+10];
   // int g[1000000];
    for(i=0;i<=m;i++) g[i]=-1;
    sort(v.begin(),v.end(),sortcomp);
    for(muchie i:v)
    {
        if(find(g,i.out)!=find(g,i.in))
        {
            cs=cs+i.cost;
            k++;
            g[find(g,i.out)]=i.in;
            x[l++]=i;
            //g1<<i.in<<" "<<i.out<<endl;
        }
    }
    
    g1<<cs<<endl<<k<<endl;
    //for(muchie i:x)
       // g1<<i.out<<"  "<<i.in<<" ";
    for(i=0;i<k;i++)
        g1<<x[i].out<<" "<<x[i].in<<endl;
    return 0;
}