#include <fstream>
#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, i, j, x, y, c, dist[200005], ans, parent[200005], sze[200005], parent2[200005];
set <tuple<int, int, int>> s;
int find_set(int nod)
{
    if(nod==parent[nod])
        return nod;
    return parent[nod]=find_set(parent[nod]);
}
void union_set(int a, int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
    {
        if(sze[a]<sze[b])
            swap(a, b);
        parent[b]=a;
        sze[a]+=sze[b];
    }
}
int main()
{
    fin>>n>>m;
    for(i=1; i<=n; i++)
    {
        sze[i]=1;
        parent[i]=i;
    }
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        s.insert(make_tuple(c, x, y));
    }
    for(auto i: s)
    {
        int c=get<0>(i);
        int x=get<1>(i);
        int y=get<2>(i);
       // fout<<c<<" "<<x<<" "<<y<<'\n';
        if(find_set(x)!=find_set(y))
        {
            ans+=c;
            union_set(x, y);
            parent2[x]=y;
        }
    }
    fout<<ans<<'\n';
    fout<<n-1<<'\n';
    for(i=1; i<=n; i++)
        if(parent2[i])
            fout<<i<<" "<<parent2[i]<<'\n';
    return 0;
}