#include<bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX = 400000;
const int N = 200000;

struct graf{
    int x,y,c;
};
graf v[NMAX];

vector<pair <int,int> > sol;
int n,m,RG[N + 10],tata[N + 10],sl;

void read_init()
{

    in>>n>>m;
    int a,b,c;
    for(int i = 1 ;  i <= m ; i++){
        in>>a>>b>>c;
        v[i].x = a;
        v[i].y = b;
        v[i].c = c;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        RG[i] = 1;
        tata[i] = i;
    }
}

int query(int x)
{

    int R,y;
    for(R = x ; R != tata[R] ; R = tata[R]);

    for(; tata[x] != x ;){
        y = tata[x];
        tata[x] = R;
        x = y;
    }
    return R;
}

void unire(int x,int y){

    if(RG[x] > RG[y])
        tata[y] = tata[x];
    else
        tata[x] = tata[y];
    if(RG[x] == RG[y])
        ++RG[y];
}

bool cmp(graf a,graf b)
{

    return a.c<b.c;
}

void solve()
{

    sort(v+1,v+m+1,cmp);
    int muchii = 0,ct = 0;
    while(muchii != n-1){
        ++ct;
        if(query(v[ct].x) != query(v[ct].y)){
            unire(query(v[ct].x),query(v[ct].y));
            sl += v[ct].c;
            ++muchii;
            sol.push_back(make_pair(v[ct].x,v[ct].y));
        }
    }
}

void afis()
{

    out<<sl<<"\n";
    out<<n-1<<"\n";
    for(int i = 0 ; i < n-1 ; i++)
        out<<sol[i].first<<" "<<sol[i].second<<"\n";
    out.close();
}

int main()
{

    read_init();
    solve();
    afis();
    return 0;
}