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

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()
{

    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],contor++);

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

void unire(int x,int y){

    contor++;
    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 quicksort(graf v[],int left,int right)
{
    int i=left,j=right;
    int pivot = v[left + (right-left)/2].c;
    while(i<=j)
    {

        while(v[i].c<pivot)
            i++;
        while(v[j].c>pivot)
            j--;
        if(i<=j)
        {
            swap(v[i],v[j]);
            i++;
            j--;
        }
    }

    if(left < j) quicksort(v,left,j);
    if(i < right) quicksort(v,i,right);

}

void solve()
{

    quicksort(v,1,m);
    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();
    solve();
    afis();
    return 0;
}