#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream is("apm.in");
ofstream os("apm.out");

struct Edge{
    int x, y, z;
    Edge(int a = 0, int b = 0, int c = 0)
        :x(a), y(b), z (c)
    {
    }
    bool operator < (const Edge& other) const
    {
        return z < other.z;
    }

};

int n, m;
vector <Edge> g;
vector <int> h, t;
vector <Edge> arb;
int sum;

void Read();
void Write();
int Find(int k);
void Union(int x, int y);
void Solve();

int main()
{
    Read();
    Solve();
    Write();
    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n >> m;
    g= vector<Edge>(n+1);
    h = vector <int>(n+1);
    t = vector<int>(n+1);
    arb = vector<Edge>(n+1);
    for(int i = 1; i <= n; ++i)
    {
        t[i] = i;
        h[i] = 0;
    }
    int x, y, z;
    for(int i = 1; i <= m; ++i)
    {
        is >> x >> y >> z;
        g.push_back({x, y, z});
    }
    return;
}

void Solve()
{
    sort(g.begin(), g.end());
    int k = 0; // nr muchii in apm
    int c1, c2;

    for(const auto& e : g)
    {
        c1 = Find(e.x);
        c2 = Find(e.y);
        if(c1 != c2)
        {
            sum += e.z;
            arb.push_back(e);
            Union(c1, c2);
            k++;
            if(k == n - 1) break;
        }
    }
}



int Find(int x)
{
    if ( x == t[x] ) return x;
    return t[x] = Find(t[x]);
}


void Union(int x, int y)
{
    if(h[y] > h[x])
        t[x] = y;
    else
    {
        t[y] = x;
        if(h[x] == h[y])
                h[x]++;
    }
}

void Write()
{
    os << sum << '\n';
    os << n - 1 << '\n';
    for(const auto & e : arb)
    {
        if( e.x == 0 && e.y == 0 ) continue;
        os << e.x << ' ' << e.y << '\n';
    }

}