#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int NMAX=200001;
int n, m, costs=0;
bool vis[NMAX];
vector< pair<int, int> > g[NMAX], msp;


int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int u, v, c;
        in>>u>>v>>c;
        g[u].push_back(make_pair(v, c));
        g[v].push_back(make_pair(u, c));
    }

    vector<bool> vis(n+1, 0);
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > heap;
    vis[1]=1;

    for(int i=0; i<g[1].size(); i++)
    {
        int v=g[1][i].first;
        int d=g[1][i].second;
        if(!vis[v])
            heap.push(make_pair(d, v));
    }

    int minim=(1<<29);
    while(!heap.empty())
    {
        int d=heap.top().first;
        int u=heap.top().second;
        heap.pop();

        if(vis[u])
            continue;

        vis[u]=1;
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i].first;
            int duv=g[u][i].second;
            if(!vis[v])
                heap.push(make_pair(duv, v));
            msp.push_back(make_pair(u, v));
        }
        costs+=d;

    }
    out<<costs<<'\n'<<n-1<<'\n';
    for(int i=1; i<n; i++)
        out<<msp[i-1].first<<' '<<msp[i-1].second<<'\n';
    return 0;
}