#include <fstream>
#include <vector>
#include <climits>
#include <queue>
#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");
struct cmp {
    bool operator () ( pair <int, int> a, pair <int, int> b) {
        return a.second>b.second;
    }
};
priority_queue < pair <int, int> , vector < pair <int, int> > , cmp > q;

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;

    q.push({1,0});
    while (!q.empty()) {
        pair <int, int> p=q.top();
        if (viz[p.first]==1) {
            q.pop();
            continue;
        }
        int nod=p.first;
        viz[nod]=1;
        ct=ct+d[nod];
        for (j=0;j<g[nod].size();j++) {
            nv=g[nod][j].first;
            cost=g[nod][j].second;
            if (viz[nv]==0 && d[nv]>cost) {
                d[nv]=cost;
                tata[nv]=nod;
                q.push({nv, cost});
            }
        }
    }
    fout<<ct<<"\n"<<n-1<<"\n";
    for (i=2;i<=n;i++)
        fout<<i<<" "<<tata[i]<<"\n";
    return 0;
}