#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, smin=0, nr=0;
vector<int> a;
queue<pair<int,int>> SOL;
priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> Q;

void citire()
{
    fin>>n>>m;
    for(int i=0; i<=n; i++)
        a.push_back(i);
    for(int i=1; i<=m; i++){
        int x, y, s;
        fin>>x>>y>>s;
        Q.push(make_pair(s,make_pair(x,y)));
    }
}

bool ciclu()
{
    auto b=Q.top();
    int x=b.second.first, y=b.second.second;
    if(a[x]==a[y]) return 1;
    return 0;
}

void ex()
{
    while(!Q.empty()){
        while(ciclu()&&!Q.empty())
            Q.pop();
        if(Q.empty()) continue;

        auto b=Q.top();
        Q.pop();
        int l=b.second.second;
        a[a[l]]=a[b.second.first];
        for(int i=1; i<=n; i++)
            if(a[i]==a[l]) a[i]=a[a[l]];

        smin+=b.first;
        nr++;
        SOL.push(b.second);
    }
    fout<<smin<<"\n"<<nr<<"\n";

    while(!SOL.empty()){
        fout<<SOL.front().first<<" "<<SOL.front().second<<"\n";
        SOL.pop();
    }
}

int main()
{
    citire();
    ex();
}