#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int N=200009,M=400009;
struct xd
{
    int x,y,c;
}v[M];
pair <int,int> sol[N];
int r[N],t[N],n,m,k,s;
int compare(xd a,xd b)
{
    return a.c<b.c;
}
int Find(int x)
{
    int y=x,z;
    for(y=x;y!=t[y];y=t[y]);
    for(;x!=t[x];)
    {
        z=t[x];
        t[x]=y;
        x=z;
    }
    return y;
}
void unite(int x,int y)
{
    if(r[x]>r[y])
        t[y]=x;
    else
        t[x]=y;
    if(r[x]==r[y])
        r[y]++;
}
void solve()
{
    for(int i=1;i<=n;i++)
        t[i]=i,r[i]=1;
    sort(v+1,v+m+1,compare);
    for(int i=1;i<=m&&k<n-1;i++)
    {
        int m1=Find(v[i].x),m2=Find(v[i].y);
        if(m1!=m2)
        {
            s+=v[i].c;
            sol[++k]={v[i].x,v[i].y};
            unite(m1,m2);
        }
    }
    fout<<s<<'\n'<<k<<'\n';
    for(int i=1;i<=k;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<'\n';
}
int main()
{
    fin.sync_with_stdio();
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    solve();
    return 0;
}