#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,ans;
const int N=2e5;
struct pct
{
    int x,y,z;
}a[N];
int tt[N],sz[N];
vector<pct>b;
bool cmp(pct X,pct Y)
{
    return X.z<Y.z;
}
void unite(int x,int y)
{
    tt[x]=y;
    sz[y]+=sz[x];
}
int get_root(int x)
{
    if(tt[x]!=x)
        return tt[x]=get_root(tt[x]);
    return x;
}
signed main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].z;
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=n;i++)
        tt[i]=i,sz[i]=1;
    int nr=n,i=1;
    while(nr!=1)
    {
        int X=get_root(a[i].x);
        int Y=get_root(a[i].y);
        if(X!=Y)
        {
            nr--;
            ans+=a[i].z;
            unite(X,Y);
            b.push_back({a[i].x,a[i].y,0});
        }
        i++;
    }
    g<<ans<<'\n'<<n-1<<'\n';
    for(auto x: b)
        g<<x.x<<" "<<x.y<<'\n';
    return 0;
}