#include <bits/stdc++.h>

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