#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("kurskal.in");
//ofstream cout("kruskal.out");
const int nmax=101;
struct elem{
    int x,y,cost;
};
int n,m,x,y,cost;
vector<elem> v;
vector< pair<int,int> >ans;
int conex[nmax],tata[nmax];
long long suma;
bool cmp(const elem a,const elem b)
{
    return a.cost<b.cost;
}
int par(int x)
{
    if(tata[x]==x)
        return x;
    return tata[x]=par(tata[x]);
}
void union_set(int a, int b, int cost)
{
    int p1=par(a);
    int p2=par(b);
    if(p1!=p2)
    {
        if(conex[p1]<conex[p2])
            swap(p1,p2);
        conex[p1]+=conex[p2];
        tata[p2]=p1;
        suma+=cost;
        ans.push_back({a,b});
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>cost;
        v.push_back({x,y,cost});
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=1;i<=n;i++)
    {
        tata[i]=i;
        conex[i]=1;
    }
    for(auto e:v)
    {
        union_set(e.x,e.y,e.cost);
    }
    cout<<suma<<'\n';
    cout<<ans.size()<<'\n';
    for(auto e:ans)
        cout<<e.first<<' '<<e.second<<'\n';
}