#include <fstream>
#include <queue>
#include <vector>
#define DMAX 200005

using namespace std;

struct muchie {
    int cost, dest, plec;
    bool operator < (const muchie &A) const {
        return A.cost < cost;
    }
};

muchie temp;

vector <muchie> edges[DMAX];

priority_queue <muchie> pq;

muchie ans[DMAX];

int n, a, b, c, cost_final, node_add, m;

int vis[DMAX];

void solve(){
    for(int i = 2; i <= n; ++i){
        temp = pq.top();
        pq.pop();
        while(vis[temp.dest]){
            temp = pq.top();
            pq.pop();
        }
        cost_final += temp.cost;
        ans[i-1] = temp;
        node_add = temp.dest;
        vis[node_add] = 1;
        for(int j = 0; j < edges[node_add].size(); ++j){
            if(!vis[edges[node_add][j].dest])
                pq.push(edges[node_add][j]);
        }
    }
}

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in>>n>>m;
    for(int i = 1; i <= m; ++i){
        in>>a>>b>>c;
        temp.plec = a;
        temp.dest = b;
        temp.cost = c;
        edges[a].push_back(temp);
        temp.dest = a;
        temp.plec = b;
        edges[b].push_back(temp);
    }
    vis[1] = 1;
    for(int i = 0; i < edges[1].size(); ++i){
        pq.push(edges[1][i]);
    }
    solve();
    out<<cost_final<<"\n"<<n - 1<<"\n";
    for(int i = 1; i < n; ++i){
        out<<ans[i].dest<<" "<<ans[i].plec<<"\n";
    }
    in.close();
    out.close();
    return 0;
}