#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

const int N = 200001;
const int M = 400001;

struct edge_type{
    int from;
    int to;
    int cost;

    edge_type(int From, int To, int Cost){
        from = From;
        to = To;
        cost = Cost;
    }
};

auto cmp_edges = [](edge_type A, edge_type B){ return A.cost > B.cost; };
int n,m;
list<edge_type> neighbours[N];
priority_queue<edge_type, vector<edge_type>, decltype(cmp_edges)> edges(cmp_edges);
bool visited[N]; // = {0, 0, ...}
int total_cost = 0;
vector<edge_type> tree_edges;

void visit_node(int index){
    if(visited[index]) cout<<"Pai deja m-ai vizitat, futu-ti mortii ma-tii :D\n";
    //cout<<"Visited "<<index<<"\n";

    visited[index] = true;
    for(auto &neighbour : neighbours[index])
    {
        edges.push(neighbour);
        //cout<<"Pushed edge to "<<neighbour.to<<" with cost "<<neighbour.cost<<"\n";
    }
    //cout<<"Current edges top: "<<edges.top().to<<"\n";
}

void print_neighbours(){
    for(int i=1; i<=n; ++i){
        cout<<i<<": ";
        for(auto &neighbour : neighbours[i])
            cout<<"("<<neighbour.to<<","<<neighbour.cost<<") ";
        cout<<"\n";
    }
    cout<<"\n";
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin>>n>>m;
    for(int i=0; i<m; ++i){
        int from, to, cost;
        cin>>from>>to>>cost;

        neighbours[from].push_back(*(new edge_type(from, to, cost)));
        neighbours[to].push_back(*(new edge_type(to, from, cost)));
    }

    //print_neighbours();

    visit_node(1);
    while(edges.size()){
        edge_type crt_edge = edges.top();
        edges.pop();

        //cout<<"crt_edge.to = "<<crt_edge.to<<"\n";
        if(!visited[crt_edge.to]){
            //cout<<"Visiting "<<crt_edge.to<<"\n";
            visit_node(crt_edge.to);
            tree_edges.push_back(crt_edge);
            total_cost += crt_edge.cost;
        }
    }

    cout<<total_cost<<"\n";
    cout<<n-1<<"\n";
    for(auto &edge:tree_edges)
        cout<<edge.from<<" "<<edge.to<<"\n";

    return 0;
}