#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
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< tuple<int, int, int>, vector< tuple<int, int, int> >, greater< tuple<int, 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_tuple(d, v, 1));

    }

    int minim=(1<<29);
    while(!heap.empty())
    {
        int d=get<0>(heap.top());
        int u=get<1>(heap.top());
        int que=get<2>(heap.top());
        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_tuple(duv, v, u));

        }
        costs+=d;
        msp.push_back(make_pair(u, que));
    }
    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;
}