#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,v[200000],vvv[3][200000],i,j,cost,ii=1,cmin,variabila_inutila;
queue <int> Q;
struct cell{
    int x,y,co;
}w[200000];
bool fcost(cell a, cell b){
    return a.co<b.co;
}
/*void BF(){
    int i,x;
    Q.push(1);
    v[1]++;
    while(!Q.empty())
    {
        x=Q.front();
        for(i=1;i<=n;i++)
            if(a[x][i]>0 && v[i]==0)
            {
                Q.push(i);
                v[i]=1;
            }
        fout<<x<<" ";
        Q.pop();
    }
}
void DF(int k){
    int i;
    fout<<k<<" ";
    v[k]=1;
    for(i=1;i<=n;i++)
        if(a[k][i]>0 && v[i]==0)
            DF(i);
}*/
void Kruskal(){
    int i,k=1;
    for(i=1;i<=n;i++)
        v[i]=i;
    sort(w+1,w+ii,fcost);
    for(i=1;i<ii;i++)
    {
        if(v[w[i].x]!=v[w[i].y] && k<n)
        {
            variabila_inutila=v[w[i].y];
            for(int j=1;j<=n;j++)
                if(v[j]==variabila_inutila)
                    v[j]=v[w[i].x];
            vvv[1][k]=w[i].y;
            vvv[2][k]=w[i].x;
            cmin+=w[i].co;
            k++;
        }
    }
    fout<<cmin<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        fout<<vvv[1][i]<<" "<<vvv[2][i]<<'\n';
}
int main(){
    fin>>n>>m;
    while(fin>>i>>j>>cost)
    {
        w[ii].x=i;
        w[ii].y=j;
        w[ii].co=cost;
        ii++;
    }
    //BF();
    //DF(1);
    Kruskal();
    fin.close();
    fout.close();
    return 0;
}