#include <vector>
#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 n,m,i,j,x,y,z;
int d[MAXN], tata[MAXN];
bool fol[MAXN];

void prim(int nod)
{
    d[nod] = 0;
    coada.push( make_pair(0, nod));
    while(!coada.empty())
    {
        int crt_nod = coada.top().second; fol[ crt_nod ] = true;
        int crt_cost = -coada.top().first;
        coada.pop();

        if( crt_cost > d[ crt_nod ])
            continue;

        for(int i=0; i<graf[ crt_nod ].size(); i++)
            if(!fol[ graf[crt_nod][i].second ] && d[ graf[crt_nod][i].second ] > graf[crt_nod][i].first )
            {
                d[ graf[crt_nod][i].second ] = graf[crt_nod][i].first;
                tata[ graf[crt_nod][i].second ] = crt_nod;
                coada.push( make_pair(-d[ graf[crt_nod][i].second ], graf[crt_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);
}