#include <bits/stdc++.h>
using namespace std;
ifstream in("kruskal.in");
ofstream out("kruskal.out");
int n,m,suma=0,P[101],k;
struct muchie
{
    int cost,x,y;
} v[101],sol[101];
bool compare(muchie a,muchie b)
{
    return a.cost>b.cost;
}
void kruskal()
{
    int i=1;
    while(k<n-1)
    {
        if(P[v[i].x]!=P[v[i].y])
        {
            k++;
            suma=suma+v[i].cost;
            sol[k]=v[i];
            int nr1=P[v[i].x];
            int nr2=P[v[i].y];
            for(int j=1; j<=n; j++)
                if(P[j]==nr2) P[j]=nr1;
        }
        i++;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>v[i].cost>>v[i].x>>v[i].y;
        P[i]=i;
    }
    sort(v+1,v+1+m,compare);
    kruskal();
    cout<<suma<<endl;
    for(int i=1; i<=k; i++)
        cout<<sol[i].x<<" "<<sol[i].y<<endl;
}