#include <bits/stdc++.h>

using namespace std;
struct legaturi
{
    int pos1,pos2,cost;
};
vector<legaturi>nod;
vector<pair<int,int> >ans;
bitset<200005>ap;
int x,y,c,n,m;
int parent[200005],sons[200005];
bool cmp(legaturi a,legaturi b)
{
    if(a.cost==b.cost)
    {
        if(a.pos1==b.pos1)
            return a.pos2<b.pos2;
        return a.pos2<b.pos2;
    }
    return a.cost<b.cost;
}
void solve()
{
    int howmany=0;
    int counter=0;
    for(int i=1;i<=n;i++)
    {
        parent[i]=-1;
        sons[i]=1;
    }
    int mx=0;
    for(int i=0;i<m;i++)
    {
        int first=nod[i].pos1;
        while(parent[first]!=-1)
            first=parent[first];
        int second=nod[i].pos2;
        while(parent[second]!=-1)
            second=parent[second];
        if(first==second)
            continue;
        if(sons[first]>=sons[second])
        {
            parent[second]=first;
            sons[first]+=sons[second];
            if(sons[first]>mx)
                mx=sons[first];
        }
        else
        {
            parent[first]=second;
            sons[second]+=sons[first];
            if(sons[second]>mx)
                mx=sons[second];
        }
        if(ap[nod[i].pos1]==0)
        {
            howmany++;
            ap[nod[i].pos1]=1;
        }
        if(ap[nod[i].pos2]==0)
        {
            howmany++;
            ap[nod[i].pos2]=1;
        }
        ans.push_back({nod[i].pos1,nod[i].pos2});
        counter+=nod[i].cost;
        if(howmany==n && mx==n)
            break;
    }
    printf("%d\n%d\n",counter,ans.size());
    for(int i=0;i<ans.size();i++)
        printf("%d %d\n",ans[i].first,ans[i].second);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d\n",&x,&y,&c);
        nod.push_back({x,y,c});
    }
    sort(nod.begin(),nod.end(),cmp);
    solve();
    return 0;
}