#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

vector <in> a;
vector <int> margini[100000];
vector <in> marg;
int n,m;

int cop(int x,int y,int z)
{
    for(int i=0;i<margini[x].size();i++)
        if(margini[x][i]==y)
        {
            return 0;
        }
        else return cop(margini[x][i],y,x);
    if(x==z)
        return 1;
    return 0;
}

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

    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        in x;
        scanf("%d %d %d",&x.x,&x.y,&x.c);
        a.push_back(x);
    }
    for(int i=0;i<m-1;i++)
        for(int j=i+1;j<m;j++)
        if(a[i].c>a[j].c)
    {
        in aux=a[i];
        a[i]=a[j];
        a[j]=aux;
    }
    /**
    for(int i=0;i<m;i++)
        cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].c<<endl;*/
    for(int i=0;i<=n;i++)
        margini[i].push_back(i);
    for(int i=0;i<m;i++)
    {
        int x=a[i].x,y=a[i].y;
        int ok=1;
        ok=cop(x,y,x);
        if(ok)
        {
            margini[x].push_back(y);
            //margini[y].push_back(x);
            in c;
            c.x=x,c.y=y,c.c=a[i].c;
            marg.push_back(c);
        }
        /**for(int i=0;i<=n;i++)
        {
            for(int j=0;j<margini[i].size();j++)
                cout<<margini[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;*/
    }

    int s=0;
    for(int i=0;i<marg.size()-1;i++)
        s+=marg[i].c;
    cout<<s<<endl<<marg.size()-1<<endl;
    for(int i=0;i<marg.size()-1;i++)
        {
            cout<<marg[i].x<<" "<<marg[i].y;
            cout<<endl;
        }
    return 0;
}