#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <list>
#include <tuple>
#define mt make_tuple
#define pb push_back
#define loop(i,a,b) for(int i=a;i<b;i++)
#define lit(it) list<tuple<int,int>>::iterator

using namespace std;

vector<list<tuple<int,int>>> edges;
map<int,bool> marked;
vector<tuple<int,int,int>> sortedEdges;
list<tuple<int,int>> treeEdges;
int nrVertex,nrEdges;
int SUM=0;

void vec_insert(tuple<int,int,int> edge)
{
    int a=0,b=sortedEdges.size();
    int auxPound = get<2>(edge);
    while(a!=b)
    {
        int m=a+b/2;
        int auxPound2 = get<2>(sortedEdges[m]);
        if(auxPound2<auxPound)
            b=m;
        else if(auxPound2==auxPound)
            a=b=m;
        else
            a=m+1;
    }
    sortedEdges.insert(sortedEdges.begin()+a,edge);
}


int
BinarySearch (int low, int high, int key)
{
    int mid,a;

    if (low == high)
        return low;

    mid = low + ((high - low) / 2);
    a=get<2>(sortedEdges[mid]);

    if (key < a)
        return BinarySearch (mid + 1, high, key);
    else if (key > a)
        return BinarySearch (low, mid, key);

    return mid;
}


void addEdges(int x)
{
    while(edges[x].empty()==0)
    {
        tuple<int,int> edge = edges[x].back();
        edges[x].pop_back();
        int poz = BinarySearch(0,sortedEdges.size(),get<1>(edge));
            sortedEdges.insert(sortedEdges.begin()+poz,
                               mt(x,get<0>(edge),get<1>(edge)));
    }
}
int main()
{
    ifstream in("apm.in");
    in>>nrVertex>>nrEdges;

    edges.resize(nrVertex+1);

    loop(i,0,nrEdges)
    {
        int x,y,c;
        in>>x>>y>>c;
        edges[x].pb(mt(y,c));
        edges[y].pb(mt(x,c));
    }

    in.close();

    marked[1]=1;
    addEdges(1);

    for(int i=1;i<nrVertex;i++)//while(true)
    {
        tuple<int,int,int> edge;
        do
        {
            edge=sortedEdges.back();
            sortedEdges.pop_back();
        } while(marked[get<1>(edge)]!=0);
        marked[get<1>(edge)]=1;
        cout<<get<0>(edge)<<" ";
        cout<<get<1>(edge)<<" ";
        cout<<get<2>(edge)<<endl;

        treeEdges.push_back(mt(get<0>(edge),get<1>(edge)));

        addEdges(get<1>(edge));
        SUM+=get<2>(edge);
    }

    ofstream out("apm.out");

    out<<SUM<<endl<<treeEdges.size()<<endl;
    for(list<tuple<int,int>>::iterator it=treeEdges.begin();it!=treeEdges.end();it++)
    {
        out<<get<0>(*it)<<" ";
        out<<get<1>(*it)<<endl;
    }

    out.close();

    return 0;
}