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

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

int N, M, x, y, z;
vector <pair<int,int> > G[200001];
vector <pair<int,int> > Edge;
int minCost;
int D[200001];
int T[200001];
bool Vis[200001];
priority_queue <pair<int,int> , vector <pair<int,int> >, greater<pair<int,int> > > P;

void Input();
void Prim();
void Output();

int main()
{
    Input();
    Prim();
    Output();

    is.close();
    os.close();
}

void Input()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y >> z;
        G[x].push_back(make_pair(y,z));
        G[y].push_back(make_pair(x,z));
    }
    int f = ((1<<31)-1);
    for ( int i = 1; i <= N; ++i )
        D[i] = f;
}

void Prim()
{
    P.push(make_pair(0,1));
    D[1] = 0;
    int node, cost;
    while ( !P.empty() )
    {
        node = P.top().second;
        minCost += P.top().first;
        Vis[node] = 1;
        P.pop();
        for ( const auto& v : G[node] )
        {
            if ( D[v.first] > v.second && Vis[v.first] == false )
            {
                D[v.first] = v.second;
                T[v.first] = node;
                P.push(make_pair(v.second,v.first));
            }
        }
        if ( node != 1 )
            Edge.push_back(make_pair(T[node],node));

        while ( !P.empty() && Vis[P.top().second] )
            P.pop();
    }
}

void Output()
{
    os << minCost << '\n';
    os << Edge.size() << '\n';
    for ( int i = 0; i < Edge.size(); ++i )
    {
        os << Edge[i].first << " " << Edge[i].second << '\n';
    }
}