#include <bits/stdc++.h>

using namespace std;

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

struct muchie
{
    int x,y,cost;
}a[405];

struct
{
    int x,y;
}afis[205];

int t[205],n,m,s,k,i;

bool cmp(muchie i,muchie j)
{
    return(i.cost<j.cost);
}

int r(int a)
{
    if(t[a]!=0)
    {
        int k=r(t[a]);
        t[a]=k;
        return k;
    }
    return a;
}

void unire(int x,int y)
{
    int ry=r(y),rx=r(x);
    if(rx!=ry)
    {
        s+=a[i].cost;
        t[ry]=rx;
        afis[++k].x=x;
        afis[k].y=y;
    }
}

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
        in>>a[i].x>>a[i].y>>a[i].cost;
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++)
        unire(a[i].x,a[i].y);
    out<<s<<'\n'<<n-1<<'\n';
    for(int i=1;i<n;i++)
        out<<afis[i].x<<' '<<afis[i].y<<'\n';
    return 0;
}