#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>rang,T;

int radacina(int x)
{
    if(T[x]==x)return x;
    int rad=radacina(T[x]);
    T[x]=rad;//aduc "mai aproape" rad
    return T[x];
}

void unite(int x,int y)
{
    if(rang[x]<rang[y])
        T[y]=x;
    else
    {
        if(rang[x]==rang[y])
            rang[y]++;
        T[x]=y;
    }
}

void kruskal()
{
    for(auto&m:M)
    {
        int rx=radacina(m.x),ry=radacina(m.y);
        if(rx!=ry)
        {
            unite(rx,ry);
            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());
    T=rang=vector<int>(n+1,0);
    for(int i=1;i<=n;i++)T[i]=i;
    kruskal();
    cout<<cost<<'\n'<<sol.size()<<'\n';
    for(auto&i:sol)cout<<i.x<<" "<<i.y<<'\n';
    return 0;
}