#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

#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 dfs(int nod)
{
    if(VER[nod]) return;
    VER[nod] = 1;
    for(unsigned int i = 0; i < VECT1[nod].size(); i++)
        dfs(VECT1[nod][i]);

}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d%d",&N,&M);
    int x,y,c;
    for(int i = 1; i <= M; i++)
    {
        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());

    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));
        dfs(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%d\n",ANS,N-1);//dc N - 1??
    for(int i = 0;i < N - 1; ++i)
        printf("%d %d\n",VANS[i].first,VANS[i].second);
    return 0;
}