#include <bits/stdc++.h>
using namespace std;

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

typedef pair<int,int> pr;
int n,m,a,b,val,i,viz[200005],dist[200005],tata[200005],nod,vecin,suma;
vector<pair<int,int>> v[200005];
priority_queue<pr,vector<pr>,greater<pr>> pq;

int main()
{
fin>>n>>m;
for(i=1;i<=n;i++){
    dist[i] = 1000000000;
}
for(i=1;i<=m;i++){
    fin>>a>>b>>val;
    v[a].push_back({b,val});
    v[b].push_back({a,val});
}
dist[1] = 0;
pq.push({0,1});
while(pq.empty() == false){
    nod = pq.top().second;
    pq.pop();
    if(viz[nod] == 0){
    viz[nod] = 1;
    for(i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        val = v[nod][i].second;
        if(val < dist[vecin] && viz[vecin] == 0){
            dist[vecin] = val;
            pq.push({val,vecin});
            tata[vecin] = nod;
        }
    }
    }
}
for(i=2;i<=n;i++){
    suma += dist[i];
}
fout << suma << '\n';
fout << n - 1 << '\n';
for(i=2;i<=n;i++){
    fout << i << " " << tata[i] << '\n';
}
    return 0;
}