#include <fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");


struct muchie
{
    int x,y,c;
    bool operator < (const muchie&other)const
    {
        return c<other.c;
    }
};
vector<muchie>M,sol;
int n,m,cost,nrmuchii;
vector<int>viz;

void unite(int x,int y)
{
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==y)viz[i]=x;
    }
}

void kruskal()
{
    for(int i=1;i<=n;i++)viz[i]=i;
    for(auto&m:M)
    {
        if(viz[m.x]!=viz[m.y])
        {
            unite(viz[m.x],viz[m.y]);
            nrmuchii++;cost+=m.c;
            sol.push_back(m);
            if(nrmuchii==n-1)break;
        }
    }
}


int main()
{
    cin>>n>>m;
    viz=vector<int>(n+1,0);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;cin>>x>>y>>c;
        M.push_back({x,y,c});
    }
    sort(M.begin(),M.end());
    kruskal();
    cout<<cost<<'\n'<<sol.size()<<'\n';
    for(auto&i:sol)cout<<i.x<<" "<<i.y<<'\n';
    return 0;
}