# include <cstdio>
# include <set>
# include <vector>
# define F first
# define S second

using namespace std;
int t[200010],r[200010];
int i,n,m,x,y,C,c;
multiset < pair< int, pair<int, int > > > h;
multiset < pair< int, pair<int, int > > > :: iterator it;
vector < pair< int, int> > sol;
int find(int x)
{
    if(t[x]!=x) t[x]=find(t[x]);
    return t[x];
}
void merge(int x, int y)
{
    if(r[x]>r[y]) t[y]=x;
    else t[x]=y;
    if(r[x]==r[y]) r[x]++;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d\n", &n, &m);
    for(; m; m--)
    {
        scanf("%d %d %d\n", &x, &y, &c);
        h.insert(make_pair(c,make_pair(x,y)));
    }
    for(i=1; i<=n; ++i)
    {
        t[i]=i;
        r[i]=1;
    }
    for(it=h.begin(); it!=h.end() && sol.size()<n; ++it)
    {
        x=find((*it).S.F);
        y=find((*it).S.S);
        if(x!=y)
        {
            C+=(*it).F;
            sol.push_back(make_pair((*it).S.F , (*it).S.S));
            merge(x,y);
        }
    }
    printf("%d\n%d\n", C, n-1);
    for(i=0; i<n-1; ++i)
        printf("%d %d\n", sol[i].F, sol[i].S);
    return 0;
}