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

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

struct Edge{
    int x, y, w;

    bool operator < ( const Edge& a ) const
    {
        return w < a.w;
    }
};
using VI = vector<int>;
int N, M;
vector<Edge> G;
vector<pair<int, int>> v;
VI l, t;
int cmin;

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

int main()
{
    Read();
    Kruskal();
    Write();

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int x, y, w;

    fin >> N >> M;
    l = t = VI(N + 1);
    while ( M-- )
    {
        fin >> x >> y >> w;
        G.push_back({x, y, w});
    }
}

void Kruskal()
{
    sort(G.begin(), G.end());

    for ( int i = 1; i <= N; ++i )
        l[i] = 1, t[i] = i;

    for ( const auto& x : G )
    {
        int a = x.x;
        int b = x.y;
        int c1 = Find(a), c2 = Find(b);

        if ( c1 != c2 )
        {
            cmin += x.w;
            v.push_back({a, b});
            Union(c1, c2);
        }
    }
}

void Write()
{
    fout << cmin << '\n' << N - 1 << '\n';

    for ( const auto& x : v )
        fout << x.first << ' ' << x.second << '\n';
}

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

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