#include <bits/stdc++.h>


using namespace std;

struct cows
{
    int a,b,val;
} ;

cows v[400005];
int prt[200005];
int vl[200005];
vector<int>lst;

int Find(int a)
{
    if(prt[a]==a)
        return a;
    return prt[a]=Find(prt[a]);
}

void unite(int x,int y)
{
    if(vl[x]<vl[y])
        swap(x,y);
    prt[y]=x;
    vl[x]+=vl[y];
    vl[y]=0;
}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    priority_queue<pair<int,int>>pq;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        prt[i]=i;
        vl[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>v[i].a>>v[i].b>>v[i].val;
        pq.push({-v[i].val,i});
    }
    int sum=0;
    while(!pq.empty())
    {
        int x=pq.top().first*-1;
        int y=pq.top().second;
        pq.pop();
        int x2=v[y].a;
        int y2=v[y].b;
        x2=Find(x2);
        y2=Find(y2);
        if(x2!=y2)
        {
            unite(x2,y2);
            lst.push_back(y);
            sum+=x;
        }
    }
    cout<<sum<<'\n';
    cout<<lst.size()<<'\n';
    for(auto i:lst)
    {
        cout<<v[i].a<<" "<<v[i].b<<'\n';
    }

    return 0;
}