#include <bits/stdc++.h>
using namespace std ;
ifstream f ("apm.in") ;
ofstream g ("apm.out") ;
int N , M  ;
long long Cost = 0;
struct Muchie
{
    int x;
    int y;
    int c;
}v[400010];
int t[200010] , h[200010] ;
struct q
{
    int X ;
     int Y;
}V[400010];
int muchie (int x , int y)
{
        int x1 , y1 , c;
    int r1 = x;
    int r2 = y;
    while (t[r1] ) r1 = t[r1] ;
    while (t[r2] ) r2 = t[r2] ;

        if (r1 == r2) return 0 ;

while (t[x] )
{
    x1 = t[x] ;
    t[x] = r1 ;
    x  = x1;
}
while (t[y] )
{
    y1 = t[y];
    t[y] = r2;
    y= y1;
}
        if (h[r2] < h[r1])
        {
            t[r2] = r1 ;
            c = r1;
        }
        else
        {
            t[r1] = r2;
            c = r2;
        }
        if (h[r2] == h[r1]) h[c] ++ ;
}
bool cmp(Muchie a , Muchie b)
{
    if (a.c < b.c) return true;
    return false;
}
void Kruskal ()
{
    int i = 1 , k = 0 ;
    while (k < N - 1)
    {
        if (muchie (v[i].x , v[i].y))
        {
            Cost += v[i].c;
            k ++ ;
           V[k].X = v[i].x;
           V[k].Y = v[i].y;

        }
        i ++ ;
    }

}
int main()
{
    f >> N >> M ;
    for (int i = 1 ; i <= M ; ++i)
        f >> v[i].x >> v[i].y >> v[i].c ;

    for (int i = 1 ; i <= N ; ++i)
        h[i] = 1 ;
    sort(v + 1 , v + M + 1 , cmp) ;

    Kruskal() ;

    g << Cost << endl << N - 1 << endl ;
    for (int i =  1; i <= N - 1 ; ++i)
        g << V[i].Y << ' '<< V[i].X << endl;
}