#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 200010

using namespace std;
struct muchie
{
    int x,y,c;
};

int k,n,m,con[Nmax],cost;
vector <muchie> M,sol;
const char inFile[] = "apm.in";
const char outFile[] = "apm.out";

int cmp(muchie A,muchie B)
{
    return A.c < B.c;
}

void Kruskal()
{
    int j,i = 0;
    while(k < n - 1)
    {
        if(con[M[i].x] != con[M[i].y])
        {
            k++;
            for(j=1;j<=n;j++)
                if(con[j] == con[M[i].x])
                    con[j] = con[M[i].y];

            cost += M[i].c;
            //printf("%d %d\n",M[i].x,M[i].y);
            sol.push_back(M[i]);
        }
        i++;
    }
}

int main()
{
    int i;
    muchie a;
    freopen(inFile,"r",stdin);
    freopen(outFile,"w",stdout);

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        con[i] = i;

    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a.x,&a.y,&a.c);
        M.push_back(a);
    }

    sort(M.begin(), M.end(), cmp);
    Kruskal();

    printf("%d\n%d\n",cost,k);

    for(i=0;i<k;i++)
        printf("%d %d\n",sol[i].x,sol[i].y);
}