#include <bits/stdc++.h>

#define VMAX 100
#define NMAX 200000
#define LOG 18
#define INF (long long)(10e17)
#define MOD 998244353
#define ll long long int


#define NIL 0


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

struct edge
{
    int x,y,c;
};

int dsu_root[NMAX+1],dsu_rank[NMAX+1];


int dsu_find(int x)
{
    if(x==dsu_root[x])
    {
        return x;
    }
    return dsu_root[x] = dsu_find(dsu_root[x]);
}

void dsu_unite(int x,int y)
{
    x = dsu_find(x);
    y = dsu_find(y);
    if(dsu_rank[x] < dsu_rank[y])
    {
        swap(x,y);
    }
    dsu_root[y]=x;
    dsu_rank[x] += dsu_rank[y];
}

edge edges[2*NMAX+1];
bool selected[2*NMAX+1];

bool cmp(edge a,edge b)
{
    return a.c < b.c;
}
int main()
{
    int n,m;
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        fin >> edges[i].x >> edges[i].y >> edges[i].c;
    }
    for(int i=1;i<=n;i++)
    {
        dsu_root[i]=i;
        dsu_rank[i]=1;
    }

    sort(edges+1,edges+m+1,cmp);

    ll costApm=0;
    for(int i=1;i<=m;i++)
    {
        int x = edges[i].x;
        int y = edges[i].y;
        int c = edges[i].c;

        if(dsu_find(x) != dsu_find(y))
        {
            costApm += c;
            selected[i]=1;
            dsu_unite(x,y);
        }
    }
    fout << costApm << '\n' << n-1 << "\n";
    for(int i=1;i<=m;i++)
    {
        if(selected[i])
        {
            fout << edges[i].x << " " << edges[i].y << '\n';
        }
    }
}