#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream be("apm.in");
ofstream ki("apm.out");

int findset(int i,vector<int>&parent)
{
    if(i==parent[i])
        return i;
    else findset(parent[i],parent);
}

void unionset(int x,int y,vector<int>&parent)
{
    parent[x]=parent[y];
}

void kruskal(vector<pair<int,pair<int,int> > >&adj,vector<pair<int,pair<int,int> > >&t,vector<int>&parent,int &db)
{
    int xRep,yRep;
    sort(adj.begin(),adj.end());
    for(int i=0;i<adj.size();i++)
    {
        xRep=findset(adj[i].second.first,parent);
        yRep=findset(adj[i].second.second,parent);
        if(xRep!=yRep)
        {
            t.push_back(adj[i]);
            db+=adj[i].first;
            unionset(xRep,yRep,parent);
        }
    }

}

int main()
{
    int n,m,db=0;
    be>>n>>m;
    vector<pair<int,pair<int,int> > >adj;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        be>>x>>y>>c;
        adj.push_back({c,{x,y}});
    }
    vector<int>parent(n+1);
    for(int i=1;i<=n;i++)
        parent[i]=i;
    vector<pair<int,pair<int,int> > >t;
    kruskal(adj,t,parent,db);
    ki<<db<<endl;
    ki<<t.size()<<endl;
    for(int i=0;i<t.size();i++)
    {
        ki<<t[i].second.second<<" "<<t[i].second.first<<endl;
    }

    return 0;
}