#include <fstream>
#include <vector>
#include <climits>
#define inf INT_MAX
using namespace std;
int n, m, a, b, c, p ,d[200001], tata[200001], i, j, ct, Min, cost, nv;
bool viz[200001];
vector < pair <int, int> > g[200001];
ifstream fin ("apm.in");
ofstream fout ("apm.out");

int main () {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }

    d[1]=0;
    for (i=2;i<=n;i++)
        d[i]=inf;

    for (i=1;i<=n;i++) {
        Min=inf;
        for (j=1;j<=n;j++) {
            if (viz[j]==0 && d[j]<Min) {
                Min=d[j];
                p=j;
            }
        }
        viz[p]=1;
        ct=ct+d[p];
        for (j=0;j<g[p].size();j++) {
            nv=g[p][j].first;
            cost=g[p][j].second;
            if (viz[nv]==0 && d[nv]>cost) {
                d[nv]=cost;
                tata[nv]=p;
            }
        }
    }
    fout<<ct<<"\n"<<n-1<<"\n";
    for (i=2;i<=n;i++)
        fout<<i<<" "<<tata[i]<<"\n";
    return 0;
}