#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int lim=2*1e5;
int i,nr,n,m,cost,t[lim+10];
struct muchii
{
    int x,y,c;
}v[2*lim+10];
bool comp(muchii a,muchii b)
{
    return (a.c<b.c||(a.c==b.c&&(a.x<b.x)));
}
int papa(int n)
{
    if(n==t[n])return n;
    else return papa(t[n]);
}
void unionpapa(int x,int y)
{
    if(x>y)swap(x,y);
    t[y]=x;
}
vector <pair<int,int>>sol;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
    for(i=1;i<=n;i++)
        t[i]=i;
    sort(v+1,v+m+1,comp);
    for(i=1;i<=m;i++)
    {
        if(nr==n-1) break;
        if(papa(v[i].x)==papa(v[i].y))continue;
        cost+=v[i].c;
        unionpapa(papa(v[i].x),papa(v[i].y));
        sol.push_back({v[i].x,v[i].y});
    }
    fout<<cost<<'\n'<<sol.size()<<'\n';
    for(auto i:sol)
    {
        fout<<i.first<<" "<<i.second<<'\n';
    }

    return 0;
}