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

#define edge pair<int,int>
#define DIM 200001

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

int N, M, x, y, z, minCost;
int C[DIM], T[DIM];
bool Vis[DIM];
vector <edge> Graph[DIM];
vector <edge> Edge;
priority_queue <edge, vector<edge> , greater<edge> > P;

void Input();
void APM();
void Output();

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

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

void Input()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y >> z;
        Graph[x].push_back(make_pair(y,z));
        Graph[y].push_back(make_pair(x,z));
    }
    for ( int i = 2; i <= N; ++i )
        C[i] = 0x3f3f3f3f;
}

void APM()
{
    P.push(make_pair(0,1));
    Vis[1] = 1;
    int node, t;
    while ( !P.empty() )
    {
        node = P.top().second;
        Vis[node] = 1;
        for (const auto& v : Graph[node])
            if ( !Vis[v.first] && C[v.first] > v.second )
            {
                C[v.first] = v.second;
                T[v.first] = node;
                P.push(make_pair(v.second,v.first));
            }

        minCost += C[node];
        Edge.push_back(make_pair(T[node],node));
        while ( !P.empty() && Vis[P.top().second])
            P.pop();
    }
}

void Output()
{
    int i = 0;
    os << minCost << '\n' << Edge.size()-1 << '\n';
    for (const auto& node : Edge)
    {
        if ( i == 1 )
        {
            os << node.first << " " << node.second << '\n';
            i = 0;
        }
        i = 1;
    }
}