#include <fstream>
#include <vector>
#include <algorithm>
#define maxn 200010

using namespace std;
typedef struct
{
    int x,y,c;
}edge;
int TT[maxn],RG[maxn];
vector<edge> a;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,k,cnt,sol;
int ind[maxn];

bool cmp(edge a, edge b)
{
    if(a.c<b.c) return 1;
    return 0;
}

int find(int x)
{
    int R;
    for(R=x;R!=TT[R];R=TT[R]);

    while(x!=TT[x])
    {
        int y=TT[x];
        TT[x]=R;
        x=y;
    }
    return R;
}

void unite(int x,int y)
{
    if(RG[x]>RG[y])
       TT[y]=x;
       else TT[x]=y;
   if(RG[x]==RG[y]) RG[y]++;
}
void read()
{
    in>>n>>m;
    edge aux;
    for(int i=1;i<=m;i++)
    {
        in>>aux.x>>aux.y>>aux.c;
        a.push_back(aux);
    }


}
void solve()
{
     sort(a.begin(),a.end(),cmp);
    for(int i=1;i<=n;i++) TT[i]=i, RG[i]=1;
    k=n;
    for(int i=0;i<m;i++)
    {
        if(k==1) break;
        if(find(a[i].x)!=find(a[i].y))
        {
            sol+=a[i].c;
            k--;
            unite(find(a[i].x),find(a[i].y));
            ind[++cnt]=i;
        }
    }
}
int main()
{
    read();
    solve();
    out<<sol<<"\n"<<cnt<<"\n";
    for(int i=1;i<=cnt;i++)
     out<<a[ind[i]].x<<" "<<a[ind[i]].y<<"\n";
    return 0;
}