#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#define NMAX 200000+5
#define MMAX 400000+5
#define make(a,b,c) make_pair(make_pair(a,b),c)
#define muchie pair<pair<int,int>,int>
using namespace std;
int N,M,Total,Nr;
int root[NMAX],rang[NMAX];
muchie E[MMAX];
vector<pair<int,int> > Sol;
int crit(muchie A,muchie B){return A.second<=B.second;}
int find(int x)
{
    if(root[x]!=x) root[x]=find(root[x]);
    return root[x];
}
void unite(int x,int y)
{
    if(rang[x]<rang[y]) {root[x]=y; return;}
    if(rang[x]>rang[y]) {root[y]=x; return;}
    root[x]=y; rang[y]++;
}
int main()
{
    int i,x,y,a,b,c;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++) root[i]=i,rang[i]=1;
    for(i=1;i<=M;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        E[i]=make(a,b,c);
    }
    sort(E+1,E+M+1,crit);
    for(i=1;i<=M;i++)
    {
        x=find(E[i].first.first);
        y=find(E[i].first.second);
        if(x==y) continue;
        unite(x,y);
        Total+=E[i].second;
        Sol.push_back(make_pair(E[i].first.first,E[i].first.second));
    }
    Nr=Sol.size();
    printf("%d\n%d\n",Total,Nr);
    for(i=0;i<Nr;i++) printf("%d %d\n",Sol[i].first,Sol[i].second);
    return 0;
}