#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

//vector <pair <int,int> > graf[200005];
vector <tuple <int,int,int> > muchii;
priority_queue <tuple<int,int,int> > heap;
int tata[200005];
int h[200005];
int find_father(int x)
{
    if(x==tata[x])
        return x;
    return find_father(tata[x]);
    tata[x]=tata[tata[x]];
}
void unite(int x, int y)
{
    if(h[x]>=h[y])
    {
        tata[y]=x;
        h[x]++;
    }
    else
    {
        tata[x]=y;
        h[y]++;
    }
}
int kruskal(int N,int M)
{
    int x,y,c,t1,t2,cost=0;
    tuple<int,int,int> trei;
    int nr_muchii=0;
    while(nr_muchii!=N-1)
    {
        trei=heap.top();
        heap.pop();
        get<0>(trei)=-get<0>(trei);
        c=get<0>(trei);
        x=get<1>(trei);
        y=get<2>(trei);
        t1=find_father(x);
        t2=find_father(y);
        if(t1!=t2)
        {
            unite(t1,t2);
            muchii.push_back(trei);
            cost=cost+c;
            nr_muchii++;
        }
    }
    return cost;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int N,M,x,y,c,i;
    tuple<int,int,int> trei;
    f>>N>>M;
    for(i=1;i<=N;i++)
    {
        tata[i]=i;
        h[i]=1;
    }
    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        //graf[x].push_back(make_pair(y,c));
        //graf[y].push_back(make_pair(x,c));
        get<0>(trei)=-c;
        get<1>(trei)=x;
        get<2>(trei)=y;
        heap.push(trei);
    }
    g<<kruskal(N,M)<<endl;
    int lim=muchii.size();
    g<<lim<<endl;
    for(i=0;i<lim;i++)
    {
        g<<get<2>(muchii[i])<<" "<<get<1>(muchii[i])<<endl;
    }
    return 0;
}