#include <fstream>
#include <tuple>
#include <set>
#include <vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
set <tuple<int,int,int>> e;
vector <pair<int,int>> sol;
int sef[101];
int ef(int x)
{
    if(x==sef[x])
        return x;
    else
        return sef[x]=ef(sef[x]);
}
int main()
{
    int n,m,i,x,y,z,rez=0;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        sef[i]=i;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        e.insert(make_tuple(z,x,y));
    }
    int a,b;
    for(auto x : e)
    {
        a=ef(get<1>(x));
        b=ef(get<2>(x));
        if(a!=b)
        {
            sef[a]=b;
            rez+=get<0>(x);
            sol.push_back(make_pair(get<1>(x),get<2>(x)));
        }
    }
    cout<<rez<<'\n'<<sol.size()<<'\n';
    for(auto x : sol)
        cout<<x.first<<" "<<x.second<<'\n';
    return 0;
}