#include <bits/stdc++.h>

using namespace std;

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

priority_queue<pair<int, pair<int,int> >,vector<pair<int, pair<int,int> > >,greater<pair<int, pair<int,int> > > >h;

int n,m,s,b[200010],nr;
pair<int, pair<int,int> > v[400010],aux;
vector<pair<int,int> >l[200010];

pair<int,int> r[200010];

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    int i,k,x,y,c;
    scanf("%d%d",&n,&m);

    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&c);
        v[i]=make_pair(c,make_pair(x,y));
        l[x].push_back(make_pair(y,i));
        l[y].push_back(make_pair(x,i));
    }
    k=l[1].size();b[1]=1;
    for (i=0;i<k;i++) h.push(v[l[1][i].second]);
    while (nr<n-1){
        aux=h.top();
        h.pop();
        if (!b[aux.second.first]||!b[aux.second.second]) {
            if (!b[aux.second.first]){
                b[aux.second.first]=1;
                k=l[aux.second.first].size();
                for (i=0;i<k;i++) h.push(v[l[aux.second.first][i].second]);
            }
            if (!b[aux.second.second]){
                b[aux.second.second]=1;
                k=l[aux.second.second].size();
                for (i=0;i<k;i++) h.push(v[l[aux.second.second][i].second]);
            }
            s+=aux.first;
            r[++nr]=aux.second;
        }
    }
    printf("%d\n%d\n",s,nr);
    for (i=1;i<=nr;i++) printf("%d %d\n",r[i].first,r[i].second);
    return 0;
}

//          KRUSKAL
/*#include <bits/stdc++.h>

using namespace std;

int s,n,m,t[200010],nr,r[200010];

struct yay{
    int x,y,c;
}v[400010];

int cmp(yay a, yay b){
    return a.c<b.c;
}

int arb(int x){
    if (t[x]==x) return x;
    else return t[x]=arb(t[x]);
}

int main()
{
    int i;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    }
    sort(v+1,v+m+1,cmp);
    for (i=1;i<=n;i++) t[i]=i;
    for (i=1;i<=m;i++){
        if (arb(v[i].x)!=arb(v[i].y)){
            t[arb(v[i].x)]=v[i].y;
            s+=v[i].c;
            r[++nr]=i;
        }
    }
    printf("%d\n%d\n",s,nr);
    for (i=1;i<=nr;i++){
        printf("%d %d\n",v[r[i]].x,v[r[i]].y);
    }
    return 0;
}*/