#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie
{
    int i,j,c;
};
bool comp (const muchie a, const muchie b)
{
    return(a.c<b.c);
}
vector < muchie > graf;
vector < pair < int , int > > sol;
int n,m,i,j,c,cost,sel;
int a[200002];
int arb (int x)
{
    if(x==a[x] ) return a[x];
    a[x]=arb(a[x]);
    return a[x];
}
void uneste (int x, int y)
{
    a[arb(x)]=arb(y);
}
int main()
{
    in>>n>>m;
    for(i=1; i<=n; i++)
        a[i]=i;
    for(;m;m--)
    {
        in>>i>>j>>c;
        graf.push_back({i,j,c});
    }
    sort(graf.begin(),graf.end(),comp);
    for(vector < muchie > :: iterator it=graf.begin();it!=graf.end() && sel<n-1; it++)
    {
        if(arb(it->i)!=arb(it->j))
        {
            cost+=it->c;
            uneste(it->i,it->j);
            sel++;
            sol.push_back({it->i,it->j});
        }
    }
    out<<cost<<'\n'<<sol.size()<<'\n';
    for(vector < pair < int , int > > :: iterator it=sol.begin(); it!=sol.end(); it++)
        out<<it->first<<' '<<it->second<<'\n';
    return 0;
}