#include <bits/stdc++.h>
#define dim 200005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,ans,k;
int sugar[dim];
struct edges
{
    int x,y,cost;
}answer[dim];
vector <edges> edge;
void Read()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        edge.push_back({x,y,cost});
    }
}
inline bool cmp(edges a,edges b)
{
    return a.cost<b.cost;
}
int Group(int node)
{
    if(sugar[node]!=node)
        sugar[node]=Group(sugar[node]);
    return sugar[node];
}
void Unite(int node1,int node2)
{
    node1=Group(node1);
    node2=Group(node2);
    sugar[node1]=node2;
}
void Solve()
{
    sort(edge.begin(),edge.end(),cmp);
    for(int i=1;i<=n;++i)sugar[i]=i;
    for(int i=0;i<edge.size();++i)
    {
        int x=edge[i].x,y=edge[i].y,cost=edge[i].cost;
        if(Group(x)!=Group(y))
        {
            ans+=cost;
            answer[++k].x=x;
            answer[k].y=y;
            Unite(x,y);
        }
    }
}
void Write()
{
    g<<ans<<'\n';
    g<<n-1<<'\n';
    for(int i=1;i<n;++i)
        g<<answer[i].x<<" "<<answer[i].y<<'\n';
}
int main()
{
    Read();
    Solve();
    Write();
    return 0;
}