#include <iostream>
#include <vector>
#include <fstream>
#include <bitset>
#include <algorithm>
#include <queue>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int t[100005],r[100005];
struct muchie {
    int x,y,c;
    bool operator <(const muchie& other )const {
        return this->c<other.c;
    }
}a[400005];
void Union(int x, int y) {
    if (r[x]>r[y])
        t[y]=x;
    else {
        t[x]=y;
        if (r[x]==r[y])
            r[y]++;
    }
}
int find(int x) {
    if (t[x]==0)
        return x;
    int y=find(t[x]);
    t[x]=y;
    return y;
}
vector<pair<int,int>> sol;
int main()
{
    int n,m,s=0;
    fin>>n>>m;
    for (int i=1; i<=m; i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1);
    for (int i=1; i<=m; i++) {
        int x=find(a[i].x);
        int y=find(a[i].y);
        if (x!=y) {
            Union(x,y);
            s+=a[i].c;
            sol.push_back({a[i].x,a[i].y});
        }
    }
    fout<<s<<"\n";
    fout<<sol.size()<<"\n";
    for (auto it:sol) {
        fout<<it.first<<" "<<it.second<<"\n";
    }
    return 0;
}
// num=10,/=11,*=12,-=13,+=14,enter=15,.=16,