#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct edge
{
    int x,y;
}sol[200001];

priority_queue< pair< int,pair<int,int> >, vector< pair< int,pair<int,int> > >,greater< pair< int,pair<int,int> > > > q;

int rad[200001];

int u_find(int i)
{
    if(rad[i]==0)
        return i;
    return u_find(rad[i]);
}

void u_union(int x,int y)
{
    int i=u_find(x),j=u_find(y);
    rad[j]=i;
}

int main()
{
    int n,m,i,t=0,s=0,nrs=0,x,y,c;
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
        in>>x>>y>>c;
        q.push({c,{x,y}});
    }
    while(!q.empty() && t<n-1)
    {
        c=q.top().first;
        x=q.top().second.first;
        y=q.top().second.second;
        q.pop();
        if(u_find(x)!=u_find(y))
        {
            t++;
            s=s+c;
            u_union(x,y);
            sol[t].x=x;
            sol[t].y=y;
        }
    }
    out<<s<<"\n"<<n-1<<"\n";
    for(i=1;i<n;i++)
        out<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}