#include <bits/stdc++.h>

using namespace std;

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

#define ss second.second
#define sf second.first

vector<pair<int, pair<int, int>>> arb, sol;

struct Dsu
{
    vector<int> p;
    vector<int> sz;
    Dsu(int n)
    {
        for ( int i = 0 ; i < n ; i++ )
            p.push_back(i),sz.push_back(1);
    }
    int Find(int x)
    {
        return (p[x]==x ? x : p[x] = Find(p[x])) ;
    }
    bool Check(int x,int y)
    {
        x = Find(x);
        y = Find(y);
        if ( x==y )
            return true;
        return false;
    }
    bool Union(int x,int y)
    {
        x = Find(x);
        y = Find(y);
        if ( x==y )
            return false;
        if ( x > y )
            swap(x,y);
        sz[x] += sz[y];
        sz[y] = 0 ;
        p[y] = x;
        return true;
    }
    void Reset(int n)
    {
        p.clear();
        sz.clear();
        for ( int i = 0 ; i < n ; i++ )
            p.push_back(i),sz.push_back(1);
    }
};

int main()
{
    int n, m, x, y, c;
    fin >> n >> m;
    for(int i=0; i<m; i++) {
        fin >> x >> y >> c;
        arb.push_back({c, {x, y}});
    }
    sort(arb.begin(), arb.end());

    Dsu dsu(200005);
    pair<int, pair<int, int>> muc;
    for(int i=0; i<m; i++) {
        muc=arb[i];
        if(dsu.Check(muc.sf, muc.ss)==true) {
            continue;
        }
        dsu.Union(muc.sf, muc.ss);
        sol.push_back(muc);
    }

    int cost=0;
    for(auto elm:sol) {
        cost+=elm.first;
    }
    fout << cost << "\n";
    fout << sol.size() << "\n";
    for(auto elm:sol) {
        fout << elm.sf << " " << elm.ss << "\n";
    }
    return 0;
}