#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define NMaxVf 200000
#define Inf 10000
int n, m, r, VfMin, nrv;
//int G[NMaxVf][NMaxVf];
vector<vector<int> > G;
int p[NMaxVf], Z[NMaxVf];
int cmin[NMaxVf], CostMin;
void init(){
    int x, y, z;

    ifstream f("apm.in");
    f>>n>>m;
    G.resize(n+2, vector<int>(n+2, Inf));
    /*for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            G[i][j]=Inf;*/
    while(m--)
        f>>x>>y>>z, G[x][y]=G[y][x]=z;
    r=1;
    for(int i=1;i<=n;i++)
        cmin[i]=G[r][i],
        p[i]=r, Z[i]=1;
    Z[r]=0; p[r]=0; nrv=n-1;
}
void writeAPM(){
    int cost=0;

    for(int i=1;i<=n;i++)
        if(i!=r)
            cost+=G[i][p[i]];
    ofstream g("apm.out");
    g<<cost<<"\n"<<n-1<<"\n";
    for(int i=1;i<=n;i++)
        if(i!=r)
            g<<p[i]<<" "<<i<<"\n";
}
void prim(){
    while(nrv){
        CostMin=Inf;
        for(int i=1;i<=n;i++)
            if(Z[i] && CostMin>cmin[i]){
                CostMin=cmin[i];
                VfMin=i;
            }
        Z[VfMin]=0;
        nrv--;

        for(int i=1;i<=n;i++)
            if(Z[i] && G[i][VfMin] < cmin[i])
                p[i]=VfMin,
                cmin[i]=G[i][VfMin];
    }
}
int main(){
    init();
    prim();
    writeAPM();
    return 0;
}