#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[400005];
int t[200005] , h[200005] ;
vector <pair <int,int> > sol;
int muchie (int x , int y)
{
        int x1 , y1 , c;
    int r1 = x;
    int r2 = y;
    while (t[r1] != r1) r1 = t[r1] ;
    while (t[r2] != r2) r2 = t[r2] ;

        if (r1 == r2) return 0 ;

while (t[x] != r1)
{
    x1 = t[x] ;
    t[x] = r1 ;
    x  = x1;
}
while (t[y] != r2)
{
    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 ++ ;
            sol.push_back(make_pair(v[i].y,v[i].x));
        }
        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 , t[i] = i ;
    sort(v + 1 , v + M + 1 , cmp) ;

    Kruskal() ;

    g << Cost << endl << N - 1 << endl ;
    for (int i = 0 ; i < N - 1 ; ++i)
        g << sol[i].first << ' ' << sol[i].second << endl;
}