#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream gout("apm.out");
struct alo
{
    int a,b,c;
};
int gasire(int k,vector<int>&parent)
{
    if(!parent[k])return k;
    return parent[k]=gasire(parent[k],parent);
}
void unire(int &i,int &j,vector<int>&parent)
{
    int a=gasire(i,parent),b=gasire(j,parent);
    if(a!=b)parent[b]=a;
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    gout.tie(0);
    int n,m,i,j,c;
    fin>>n>>m;
    vector<int>parent(n+1,0);
    vector<alo>muchii;
    while(m--)
    {
        fin>>i>>j>>c;
        muchii.push_back({i,j,c});
    }
    sort(muchii.begin(),muchii.end(),[](const alo&d1,const alo&d2)->bool
    {
        return d1.c<d2.c;});
    int sum=0;
    vector<pair<int,int>>ans;
    for(auto e:muchii)if(gasire(e.a,parent)!=gasire(e.b,parent))
        {
            ans.push_back({e.a,e.b});
            sum+=e.c;
            unire(e.a,e.b,parent);
        }
    gout<<sum<<'\n'<<ans.size()<<'\n';
    for(auto e:ans)gout<<e.first<<' '<<e.second<<'\n';
    return 0;
}