#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <climits>
using namespace std;

struct xxx {int a,b,c;};
xxx sol[400005],l[400005];
int s(xxx x,xxx y)
{
    if(x.c > y.c)
        return 0;
    return 1;
}
void bucketSort(xxx arr[], int n)
{
    // 1) Create n empty buckets
    vector<xxx> b[n];

    // 2) Put array elements in different buckets
    for (int i=0; i<n; i++)
    {
       int bi = n*arr[i].c; // Index in bucket
       xxx q;
       q.a=arr[i].a;
        q.b=arr[i].b;
         q.c=arr[i].c;
       b[bi].push_back(q);
    }

    // 3) Sort individual buckets
    for (int i=0; i<n; i++)
       sort(b[i].begin(), b[i].end(),s);

    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
          arr[index++] = b[i][j];
}
char solutie[50];
ifstream in ("apm.in");
int n, m;
int i, j, ct,k=0;
int v[200005], f[400005];
int main()
{
    in >> n >> m;
    int a,b,c;
    xxx q;
    q.a=q.b=q.c=-INT_MAX+1;
    l[0]=q;
    for(i=1; i<=m; i++)
    {
        in>>l[i].a>>l[i].b>>l[i].c;
        //l.push_back(q);
    }
    make_heap(l+1,l+m+1,s);
    sort_heap(l+1,l+m+1,s);
    v[1]=1;
    ofstream g("am.out");
    for(i=1; i<=m; i++)
    {
        a=l[i].a;
        b=l[i].b;
        c=l[i].c;
        if(!f[i])
        {
            if(v[a] + v[b] ==1)
            {
                ct+=c;
                f[i]++;
                v[a]=v[b]=1;
                i=0;
               g<<a<<" "<<b<<"\n";
            }
        }
    }
    g.close();
    ifstream fin("am.out");
    ofstream gi("apm.out");
    gi  << ct<<"\n"<<n-1<<"\n";
    while(fin.getline(solutie,50))
    gi<<solutie<<"\n";
}