#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

///#define fs first
///#define sc second
using namespace std;

typedef pair<int, pair<int,int>> piii;

vector<piii> G[200010], Sol;
priority_queue < piii, vector<piii>, greater<piii>> Q;
int N, M, x, y, c, k, cost; bool sel[200010];

ifstream f("apm.in");
ofstream g("apm.out");

void load(){
    f >> N >> M;
    for( int i=1; i<=M; i++){
        f>>x>>y>>c;
        G[x].push_back({c,{x,y}});
        G[y].push_back({c,{y,x}});
    }
}

void apm ( int p){


    sel[p] = true;
    for(auto i : G[p]) Q.push(i);

    while (!Q.empty()){
        while (!Q.empty() && sel[Q.top().second.second]) Q.pop();
        if(Q.empty()) break;
        k = Q.top().second.second;
        c = Q.top().first;
        cost += c; sel[k] = true;
        Sol.push_back(Q.top());
        Q.pop();
        for(auto i: G[k])
            Q.push(i);
    }
}

int main()
{
    load();
    apm(1);
    g<<cost<<'\n'<<Sol.size()<<'\n';
    for(auto i: Sol)
        g<<i.second.first<<" "<<i.second.second<<'\n';
    return 0;
}