#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct triplet
{
    int x,y,c;

};
triplet dat[400000];

int t[200001], rank[200001];

bool CMP(triplet a, triplet b)
{
    return a.c<b.c;
}

int find_root(int x)
{
    if(x!=t[x])
        t[x] = find_root(t[x]);
    return t[x];
}

void uniune(int x, int y)
{
    int xroot = find_root(x);
    int yroot = find_root(y);

    if(rank[xroot]<rank[yroot])
        t[xroot] = yroot;
    else if(rank[yroot]<rank[xroot])
        t[yroot] = xroot;
    else
    {
        t[yroot] = xroot;
        ++rank[xroot];
    }
}

int st[200000],dr[200000],k;
int main()
{
    int n, m, x, y, c,sum=0;

    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>dat[i].x>>dat[i].y>>dat[i].c;
        if(i<=n)
        {
            t[i] = i;
            rank[i] = 1;
        }
    }

    sort(dat+1, dat+m+1, CMP);
    for(int i=1 ;i<=m;i++)
    {
        if(find_root(dat[i].x) != find_root(dat[i].y) )
        {
            sum+=dat[i].c;
            uniune(dat[i].x,dat[i].y);
            st[++k] = dat[i].x;
            dr[k] = dat[i].y;
        }
    }

    fout<<sum<<'\n'<<n-1<<'\n';
    for(int i=1;i<n;i++)
        fout<<dr[i]<<' '<<st[i]<<'\n';



    fin.close();
    fout.close();
    return 0;
}