# include <cstdio>
# include <set>
# include <vector>
# define N 200010
# define M 400010
# define pb push_back
# define sz size()
# define ed end()
# define bg begin()
# define mp make_pair
# define in insert
# define F first
# define S second

using namespace std;

int T[N],R[N];
int i,n,m,x,y,C;
multiset < pair< int, pair<int, int > > > h;
multiset < pair< int, pair<int, int > > > :: iterator it;
vector < pair< int, int> > Sol;

int find(int x)
{
    if(T[x]!=x) T[x]=find(T[x]);
    return T[x];
}
void meets(int x, int y)
{
    if(R[x]>R[y]) T[y]=x;
    else T[x]=y;
    if(R[x]==R[y]) R[x]++;
}
void load()
{
    int x,y,c;
    scanf("%d %d\n", &n, &m);
    for(; m; m--)
    {
        scanf("%d %d %d\n", &x, &y, &c);
        h.in(mp(c,mp(x,y)));
    }
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    load();
    for(i=1; i<=n; ++i)
    {
        T[i]=i;
        R[i]=1;
    }
    for(it=h.bg; it!=h.ed && Sol.sz<n; ++it)
    {
        x=find((*it).S.F);
        y=find((*it).S.S);
        if(x!=y)
        {
            C+=(*it).F;
            Sol.pb(mp((*it).S.F , (*it).S.S));
            meets(x,y);
        }
    }
    printf("%d\n%d\n", C, n-1);
    for(i=0; i<n-1; ++i)
        printf("%d %d\n", Sol[i].F, Sol[i].S);
    return 0;
}