#include <cstdio>
#include <algorithm>

using namespace std;


int n, m,nr = 0,val = 0,p = 1;

int daddy[200005], h[200005];

pair <int,int> v[400005] ;

struct muchie
{
    int x,y,z ;
};

muchie bullshit[400005] ;

bool cmp(muchie a,muchie b)
{
    if(a.z <= b.z)
        return true ;
    else
        return false ;
}

int find_daddy(int i)
{
    int ci,tata;
    ci=i;
    while( daddy[i] != i )
        {
            i = daddy[i] ;
        }
    while( daddy[ci] != ci )
    {
        tata=daddy[ci];
        daddy[ci] = i ;
        ci=tata;
    }
    return i;
}

inline bool ver(int a, int b)
{
    if( find_daddy(a) == find_daddy(b) )
        return true;
    else
        return false;
}

inline void conect(int x, int y,int i)
{
    int hardx , hardy ;
    hardx = find_daddy(x) ;
    hardy = find_daddy(y) ;
    if( h[hardx] >= h[hardy] )
    {
        if( h[hardx] == h[hardy] )
            h[hardx] ++ ;
        daddy[hardy] = hardx ;
    }
    else
    {
        daddy[hardx] = hardy ;
    }
    val = val + bullshit[i].z ;
    nr++;
    v[p].first = x ;
    v[p].second = y ;
    p++ ;
}

int main()
{
    freopen("apm.in", "r",stdin);
freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        daddy[i] = i ;
        h[i] = 1 ;
    }
    for(int i = 1 ; i<=m ; i++)
    {
        scanf("%d%d%d", &bullshit[i].x, &bullshit[i].y, &bullshit[i].z) ;
    }
    sort(bullshit + 1, bullshit + m + 1, cmp);
    for(int i = 1 ; i<=m && p!=n; i++)
    {
        if( ver(bullshit[i].x,bullshit[i].y) == 0 )
        {
            conect(bullshit[i].x,bullshit[i].y,i);
        }
    }
    printf("%d\n%d\n", val, nr);
    for(int i=1 ; i<p ; i++)
    {
        printf("%d %d\n", v[i].first, v[i].second);
    }
    return 0;
}