#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
bool v[400001];
struct muchie
{
    int first,second;
    int cost;
} cost[400001];
int t[200001],h[200001];
int findset(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
bool unionset(int x,int y)
{
    int tx=findset(x),ty=findset(y);
    if(tx==ty)return 0;
    if(h[tx]==h[ty])
    {
        h[tx]++;
        t[ty]=tx;
    }
    else if(h[tx]<=h[ty])
        t[tx]=ty;
    else
        t[ty]=tx;
    return 1;
}
bool cmp(muchie a,muchie b)
{
    return (a.cost<b.cost);
}
int main()
{
    int n,m,a,b,c,costy=0,nr=0;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d",&cost[i].first,&cost[i].second,&cost[i].cost);
    }
    for(int i=1; i<=n; i++)
        h[i]=1,t[i]=i;
    sort(cost+1,cost+m+1,cmp);
    for(int i=1; i<=m; i++)
    {
        if(nr==n-1)
        {
            out<<costy<<'\n'<<n-1<<'\n';
            for(int j=1; j<=m; j++)
                if(v[j]==1)
                    out<<cost[j].first<<" "<<cost[j].second<<'\n';
            return 0;
        }
        //if(nr<=n-1)
        if(unionset(cost[i].first,cost[i].second)==1)
            nr++,costy+=cost[i].cost,v[i]=1;
    }
    out<<costy<<endl<<n-1<<endl;
    for(int j=1; j<=m; j++)
        if(v[j]==1)
            out<<cost[j].first<<" "<<cost[j].second<<endl;
    return 0;
}