#include<bits/stdc++.h>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,t[200002];
vector<int>w;

struct arbore
{
    int x,y,cost;
} v[400002];

int root(int val)
{
    while(t[val]>0)
        val=t[val];
    return val;
}

int cmp(const arbore &a, const arbore &b)
{
    return a.cost<b.cost;
}

int main()
{
    int i,sol=0,k=0;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1; i<=n; i++)
        t[i]=-1;
    for(i=1; i<=m; i++)
    {
        int a=root(v[i].x);
        int b=root(v[i].y);
        if(a!=b)
        {
            w.push_back(v[i].y);
            w.push_back(v[i].x);
            sol+=v[i].cost;
            if(t[a]<t[b])
            {
                t[a]+=t[b];
                t[b]=a;
            }
            else
            {
                t[b]+=t[a];
                t[a]=b;
            }
        }
    }
    g<<sol<<'\n'<<n-1<<'\n';
    for(auto it:w)
    {
        k++;
        g<<it<<" ";
        if(k%2==0)
        {
            g<<'\n';
            k=0;
        }
    }
    return 0;
}