#include<bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct compare{
    bool operator()(const vector<int> &a, const vector<int> &b){
        return a[2]>b[2]; //compar dupa cost
    }
};

vector<pair<int,int>> v[100001]; //de ex 1: (2,3) unde 3 este costul
priority_queue<vector<int>,vector<vector<int>>,compare>heap;
vector<pair<int,int>> muchii;
int n,m,x,y,cost,cost_total;
int viz[10001];

void add(int node1,int node2,int cost){
    v[node1].push_back(make_pair(node2,cost));
}

void apm(int node){
    viz[node]=1;

    for(int i=0;i<v[node].size();i++){
        if(viz[v[node][i].first]==0) //parcurg lista de adiacenta si vad daca a fost vizitat fiecare nod
//bag in heap (u,v,cost(u,v))
        {
            vector<int> aux;
            aux.push_back(node);
            aux.push_back(v[node][i].first);
            aux.push_back(v[node][i].second);
            heap.push(aux);

        }
    }
    while(heap.size()!=0){
        vector<int> top;
        top=heap.top();
        heap.pop();

        if(viz[top[0]]==1 && viz[top[1]]==0) //u e in apm, dar v nu
        {
            cost_total+=top[2];
            muchii.push_back(make_pair(top[0],top[1])); //pun in muchii (u,v)
            apm(top[1]);
        }

    }

}


int main() {

    f>>n>>m;
    for(int i=0;i<m;i++){
        f>>x>>y>>cost;
        add(x,y,cost);
        add(y,x,cost);
    }
    apm(1);
    g<<cost_total<<'\n';
    g<<muchii.size()<<'\n';
    for(auto i:muchii)
        //for(int j=0;j<i.size();j++)
            g<<i.first<<" "<<i.second<<'\n';

}