#include <fstream>
#include <queue>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");
#define MAXN 200005
#define INF 0x3f3f3f3f

vector< pair<int, int > > graf[MAXN];
priority_queue< pair<int, int> > coada;

int d[MAXN],tata[MAXN];
int n,m,i,j,x,y,z;
bool fol[MAXN];

void prim(int st)
{
    int nod,cost,i;

    d[st] = 0;
    coada.push( make_pair(0, st ));
    while(!coada.empty())
    {
        nod = coada.top().second; fol [ nod ] = true;
        cost = -coada.top().first;
        coada.pop();

        if( cost > d[nod] )
            continue;

        for(i=0; i< graf[nod].size(); i++)
            if( !fol[ graf[nod][i].second ] && d[ graf[nod][i].second ] > graf[nod][i].first )
            {
                d[ graf[nod][i].second ] = graf[nod][i].first;
                tata[ graf[nod][i].second ] = nod;
                coada.push(make_pair( -graf[nod][i].first, graf[nod][i].second ));
            }
    }

    int cost_total = 0;
    for(i=1; i<=n; i++)
        cost_total += d[i];

    cout<<cost_total<<"\n"<<n-1<<"\n";

    for(i=2; i<=n; i++)
        cout<<i<<" "<<tata[i]<<"\n";
}

int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        graf[x].push_back(make_pair(z,y));
        graf[y].push_back(make_pair(z,x));
    }
    for(i=1; i<=n; i++)
        d[i] = INF;

    prim(1);
    return 0;
}