#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int dim=2e5+5;
int n,m,len,vc[dim],mn[dim];
long long sum;
bool viz[dim],pus[dim];
vector<pair<int,int> > G[dim];
set<pair<int,int> > S;
pair<int,int> sol[2*dim];
int main(){
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        f>>x>>y>>c;
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }
    viz[1]=1;
    S.insert({0,1});
    for(int i=1;i<=n;i++){
        pair<int,int> p=*S.begin();
        S.erase(p);
        swap(p.first,p.second);
        pus[p.first]=1;
        if(i>=2){
            sol[++len]={vc[p.first],p.first};
            sum+=mn[p.first];
        }
        for(int i=0;i<G[p.first].size();i++){
            int vec=G[p.first][i].first;
            int cost=G[p.first][i].second;
            if(pus[vec]){
                continue;
            }
            if(!viz[vec] or cost<mn[vec]){
                if(!viz[vec]){
                    S.insert({cost,vec});
                }
                else{
                    S.erase({mn[vec],vec});
                    S.insert({cost,vec});
                }
                viz[vec]=1;
                mn[vec]=cost;
                vc[vec]=p.first;
            }
        }
    }
    g<<sum<<'\n'<<len<<'\n';
    for(int i=1;i<=len;i++){
        g<<sol[i].first<<' '<<sol[i].second<<'\n';
    }
    return 0;
}