#include <fstream>
#include <vector>
#include <climits>

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

int n,m,i,j,x,y,c,d[200005],k,tata[200005],sol,Min,poz;
bool viz[200005];
struct arc{
    int nod,cost;
};
vector <arc> g[200005];

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        g[x].push_back({y,c});
        g[y].push_back({x,c});
    }
    for(i=2;i<=n;i++)
        d[i]=INT_MAX;
    for(i=1;i<=n;i++){
        Min=INT_MAX; poz=0;
        for(j=1;j<=n;j++)
            if(!viz[j] && d[j]<Min){
                Min=d[j];
                poz=j;
            }
        viz[poz]=1;
        sol+=Min;
        for(j=0;j<g[poz].size();j++){
            int nou = g[poz][j].nod;
            int cost = g[poz][j].cost;
            if(!viz[nou] && d[nou]>cost){
                d[nou] = cost;
                tata[nou] = poz;
            }
        }
    }
    fout<<sol<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<' '<<tata[i]<<'\n';
    return 0;
}