#include<stdio.h>
#include<vector>
#include<algorithm>
#include<memset>
#include<cassert>
#define pb push_back
#define mkp make_pair
 
using namespace std;
 
const int maxn = 400000;
 
int N,M;
int VER[maxn],NR;
int ANS,NOD;
vector<int> VECT[maxn],VECT1[maxn];
vector<pair<int,pair<int,int> > > VECTMU;
vector<pair<int,int> > VANS;
 
void dfs2(int nod)
{
    if (VER[nod])return;
    VER[nod] = 1;
    for(unsigned int i = 0;i < VECT1[nod].size();++i) dfs2(VECT1[nod][i]);
}
 
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&N,&M);
    for(int i = 1;i <= M; ++i)
    {
        int x,y,c;
        scanf("%d %d %d",&x,&y,&c);
        VECT[x].pb(y);
        VECT[y].pb(x);
        VECTMU.pb(mkp(c,mkp(x,y)));
    }
    NR = N;
    sort(VECTMU.begin(),VECTMU.end());
    NR = N;
    for(int i = 0;i < M; ++i)
    {
        int cost = VECTMU[i].first;
        int nod1 = VECTMU[i].second.first;
        NOD = VECTMU[i].second.second;
        memset(VER,0,sizeof(VER));
        dfs2(nod1);
        if (!VER[NOD]) {
            --NR;VECT1[nod1].pb(NOD);VECT1[NOD].pb(nod1);ANS += cost;
            VANS.pb(mkp(NOD,nod1));
        }
        if (NR == 1) break;
    }
 
    printf("%d\n",ANS);
    printf("%d\n",N-1);
    for(int i = 0;i < N - 1; ++i)
        printf("%d %d\n",VANS[i].first,VANS[i].second);
    return 0;
}