#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int x,y,z,cost,t[200100],i,n,m;
vector <pair<int,pair<int ,int> > >E,s;
int re(int x)
{
    if (x==t[x]) return x;
    t[x]=re(t[x]);
    return t[x];
}
void une(int x,int y)
{
    x=re(x);
    y=re(y);
    if (x==y) return;
    t[x]=re(y);
}
void kru()
{
    sort(E.begin(),E.end());
    for (i=1;i<=n;++i) t[i]=i;
    for (auto i:E)
    {
        x=i.second.first;
        y=i.second.second;
        if (re(x)!=re(y))
        {
            une(x,y);
            cost+=i.first;
            s.push_back(i);
        }
    }
}
int main()
{
    in>>n>>m;
    for (i=1;i<=m;++i)
    {
        in>>x>>y>>z;
        E.push_back({z,{x,y}});
    }
    kru();
    out<<cost<<'\n';
    out<<n-1<<'\n';
    for (i=0;i<n-1;++i)
    {
        out<<s[i].second.first<<" "<<s[i].second.second<<'\n';
    }
    return 0;
}