#include <fstream>
#include <vector>
#define dim 200005
#define inf 2147483647
#define x first
#define y second
using namespace std;

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

int n,m,i,x,y,z,k,sol,minim,ok[dim],t[dim],d[dim];
unsigned int j;
vector< pair< int, int > > L[dim];

int main(){
    fin>>n>>m;
    for (i=1;i<=m;i++){
        fin>>x>>y>>z;
        L[x].push_back(make_pair(y,z));
        L[y].push_back(make_pair(x,z));
    }
    for (i=2;i<=n;i++)
        d[i]=inf;
    while (1){
        minim=inf;
        for (i=1;i<=n;i++)
            if (!ok[i] && minim>d[i]){
                minim=d[i];
                k=i;
            }
        if (minim==inf)
            break;
        ok[k]=1;
        sol+=d[k];
        for (j=0;j<L[k].size();j++)
            if (!ok[L[k][j].x] && d[L[k][j].x]>L[k][j].y){
                d[L[k][j].x]=L[k][j].y;
                t[L[k][j].x]=k;
            }
    }
    fout<<sol<<'\n'<<(n-1)<<'\n';
    for (i=2;i<=n;i++)
        fout<<i<<" "<<t[i]<<'\n';
    fin.close();
    fout.close();
    return 0;
}