#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

#define MAXN 200005
#define INF 0x3f3f3f

vector< pair<int, int> > graf[MAXN];
priority_queue< pair<int, int> > coada;
int n,m,x,y,z,i,j;
int d[MAXN], tata[MAXN];
bool fol[MAXN];

void prim(int k)
{
    d[k] = 0; tata[k] = 0;
    coada.push(make_pair(0,k));

    while(!coada.empty())
    {
        int crt_nod = coada.top().second; fol[crt_nod] = true;
        int crt_cost = -coada.top().first;
        coada.pop();

        if(d[crt_nod] < crt_cost)
            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 )
            {
                tata[ graf[crt_nod][i].second ] = crt_nod;
                d[ graf[crt_nod][i].second ] = graf[crt_nod][i].first ;
                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);
}