#include<fstream>
#include<vector>
#include<algorithm>
#define ppp pair<int,pair<int,int>>
#define pp pair<int,int>
using namespace std;
int sum,n,m,t[200001];
fstream cin("apm.in",ios::in),cout("apm.out",ios::out);
vector<ppp>v;
vector<pp>arb;
int R(int x)
{
    int root = x;
    while(root !=t[root])
    {
        root = t[root];
    }
    return root;
}
void uni(int x,int y)
{
    t[x] = t[y];
}
void krus()
{
    int r1,r2;
    for(auto x:v)
    {
        r1 = R(x.second.first);
        r2 = R(x.second.second);
        if(r1!=r2)
        {
            uni(r1,r2);
            arb.push_back({x.second.first,x.second.second});
            sum+=x.first;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(;m;m--)
    {
        int x,y,w;
        cin>>x>>y>>w;
        v.push_back({w,{x,y}});
    }
    for(int i=1;i<=n;i++)
    {
        t[i] = i;
    }
    sort(v.begin(),v.end());
    krus();
    cout<<sum<<'\n'<<arb.size()<<'\n';
    for(auto x:arb)
    {
        cout<<x.second<<' '<<x.first<<'\n';
    }
    return 0;
}