#include <cstdio>
#define Nmax 400005
#include <vector>
#include <algorithm>
using namespace std;

struct muchie
{
    int x,y,c;
};

FILE * f=fopen("apm.in","r");
FILE * g=fopen("apm.out","w");

int n,m,t[Nmax],ind[Nmax],rasp;
muchie v[Nmax];
vector <int> ans;
int root(int node)
{
    if(t[node]==node)return node;
    t[node] = root(t[node]);
    return t[node];
}

void unire(int x,int y)
{
    t[root(x)]=root(y);
}

inline bool cmp(int x,int y)
{
    return v[x].c<v[y].c;
}

int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
        ind[i]=i;
    }
    for(int i=1;i<=n;i++)
        t[i]=i;
    sort(ind+1,ind+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(root(v[ind[i]].x)!=root(v[ind[i]].y))
        {
            rasp+=v[ind[i]].c;
            unire(root(v[ind[i]].x),root(v[ind[i]].y));
            ans.push_back(ind[i]);
        }
    }
    fprintf(g,"%d\n%d\n",rasp,ans.size());
    for(int i=0;i<ans.size();i++)
        fprintf(g,"%d %d\n",v[ans[i]].y,v[ans[i]].x);
    return 0;
}