#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

int n,m;
vector <int> ans;
struct MUCHIE { int v1,v2,c; };
MUCHIE e[400010];
int h[200010],t[200010];

class cmp
    {
    public:
        bool inline operator () (MUCHIE A, MUCHIE B)
        {
            return A.c<B.c;
        }
    };

int findr(int v)
{
    if(t[v]==v) return v;
    return t[v]=findr(t[v]);
}

void unite (int x, int y)
{
    int tx,ty;
    tx=findr(x);
    ty=findr(y);
    if(h[tx]>h[ty])
        {
            t[ty]=tx;
            h[ty]++;
        }
    else
        {
            t[tx]=ty;
            h[tx]++;
        }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int c,res=0,i,x,y,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&c);
            e[i].v1=x; e[i].v2=y; e[i].c=c;
        }
    for(i=1;i<=n;i++)
        t[i]=i,
        h[i]=1;
    sort(e+1,e+1+m,cmp());
    res+=e[1].c;
    ans.push_back(1);
    unite(e[1].v1,e[1].v2);
    for(i=2;i<=m;i++)
        if(findr(e[i].v1)!=findr(e[i].v2))
            {
                res+=e[i].c;
                unite(e[i].v1,e[i].v2);
                ans.push_back(i);
            }
    printf("%d\n%d\n",res,ans.size());
    for(i=0;i<ans.size();i++)
        printf("%d %d\n",e[ans[i]].v1,e[ans[i]].v2);
    return 0;
}