#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 200009;

typedef pair < int, pair< int, int > > Edge;
//Proprietatea unui arbore => graf conex aciclic format din N noduri si N muchii

struct cmp
{
    bool operator() (const Edge &a, Edge &b)
    {
        return (a.first < b.first);
    }
};

class APM
{
    int N;
    int M;
    int totalCost;

    vector< int > Fth;
    vector< int > Rank;

    vector < Edge > myList;
    vector < Edge > Solution;

    void Reset();
    void ReadData();

    int Find(int );
    void Union(int , int );

public :
    
    APM();

    void Solve();
    void Print();
};

void APM :: Reset()
{
    for(int i = 1; i <= N; ++i)
    {
        Fth[i] = i;
        Rank[i] = 0;
    }
}

void APM :: ReadData()
{
    ifstream in("apm.in");

    in >> N >> M;

    Fth.resize( N + 1);
    Rank.resize( N + 1);
    
    for(int x, y, c, i = 1; i <= M; ++i)
    {
        in >> x >> y >> c;
        myList.push_back( make_pair( c, make_pair(x, y) ) );
    }

    Reset();

    in.close();
}

APM :: APM()
{
    totalCost = 0;
    ReadData();
}

int APM :: Find(int x)
{
    int root = x;

    for(; root != Fth[root]; root = Fth[root]);

    while(x != Fth[x])
    {
        int temp = Fth[x];
        Fth[x] = root;
        x = temp;
    }

    return root;
}

void APM :: Union(int x, int y)
{
    if(Rank[x] > Rank[y])
    {
        Fth[y] = x;
        return;
    }

    if(Rank[y] > Rank[x])
    {
        Fth[x] = y;
        return;
    }

    Rank[x] ++;
    Fth[y] = x;
}

void APM :: Solve()
{
    sort(myList.begin(), myList.end(), cmp());

    for(int i = 0; i < M && Solution.size() < N - 1; ++i)
    {
        int node1 = Find( myList[i].second.first);
        int node2 = Find( myList[i].second.second);

        if(node1 != node2)
        {
            Solution.push_back( myList[i] );
            Union(node1, node2);

            totalCost += Solution.back().first;
        }
    }
}

void APM :: Print()
{
    ofstream out("apm.out");

    out << totalCost << '\n' << Solution.size() << '\n';
    for(vector< Edge > :: iterator it = Solution.begin(); it != Solution.end(); ++it)
    {
        out << it->second.first << ' ' << it->second.second << endl;
    }

    out.close();
}

int main()
{
    APM myAPM;

    myAPM.Solve();
    myAPM.Print();

    return 0;
}