#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#define nmax 10002

using namespace std;

ifstream in("flood.in");
ofstream out("flood.out");

struct muchie{
int x;
int y;
int c;
}Mc[nmax*30];

struct cmp{

public:
        inline bool operator()(const muchie&a,const muchie&b){return a.c<b.c;}
};

vector< pair<int,int> >Sol;
int N,M,x,y,c,cost,i,k,j;
int rang[nmax];
int T[nmax];
string sir;

int multime(int n)
{
    if(T[n]!=n)
        T[n]=multime(T[n]);
    return T[n];
}

inline void reuneste(int i,int j)
{
    if(i==j)return;
    if(rang[i]<rang[j])
        T[i]=j;
    else
        T[j]=i;
    if(rang[i]==rang[j])
        rang[i]++;
}

int main()
{
    in>>N>>M;
    getline(in,sir);
    for(i=1;i<=N;i++)
        T[i]=i;
    /*while(M--)
    {
        //in>>x>>y;
        getline(in,sir);
        i=0,x=0,y=0;
        while(sir[i]>='0'&&sir[i]<='9')
            x=x*10+sir[i++]-'0';
        i++;
        while(sir[i]>='0'&&sir[i]<='9')
            y=y*10+sir[i++]-'0';
        Mc[k].x=x,Mc[k].y=y,Mc[k++].c=0;
    }
    in>>M;
    getline(in,sir);*/
    int minus;
    while(M--)
    {
        minus=1;
        getline(in,sir);
        i=0,x=0,y=0,c=0;
        while(sir[i]>='0'&&sir[i]<='9')
            x=x*10+sir[i++]-'0';
        i++;
        while(sir[i]>='0'&&sir[i]<='9')
            y=y*10+sir[i++]-'0';
        i++;
        if(sir[i]=='-')
            minus=-1,i++;
        while(sir[i]>='0'&&sir[i]<='9')
            c=c*10+sir[i++]-'0';
        Mc[k].x=x,Mc[k].y=y,Mc[k++].c=c*minus;
    }
    sort(Mc,Mc+k,cmp());
    for(i=0;i<k;i++)
    {
        x=Mc[i].x,y=Mc[i].y,c=Mc[i].c;
        M=multime(x),j=multime(y);
        if(M!=j)
        {
            reuneste(M,j);
            cost+=c;
            Sol.push_back(make_pair(x,y));
            //out<<x<<' '<<y<<' '<<c<<'\n';
        }
    }
    out<<cost<<'\n'<<N-1<<'\n';
    for(i=0;i<Sol.size();i++)
        out<<Sol[i].first<<' '<<Sol[i].second<<'\n';
    return 0;
}