#include<cstdio>
#include<set>
#include<vector>
#include<algorithm>
#define N_MAX 200010
#define pb push_back
#define ins insert
#define mp make_pair
using namespace std;
vector <pair<int,int> > Sol;
multiset <pair<int,pair<int,int> > > H;
int Cost_Final=0, T[N_MAX], rang[N_MAX];
inline void Write_Sol()
{
    printf("%d\n%d\n",Cost_Final,Sol.size());
    for (vector < pair<int,int> > :: iterator it=Sol.begin();it!=Sol.end();++it)
        printf("%d %d\n",(*it).first,(*it).second);
}
inline void Reuneste(int x,int y)
{
    if (rang[x]<rang[y]) T[x]=y;
            else T[y]=x;
    if (rang[x]==rang[y]) rang[x]++;
}
inline int tata(int nod)
{
    if (T[nod]!=nod) T[nod]=tata(T[nod]);
    return T[nod];
}
inline void Load_Data()
{
    int N,M,x,y,c;
    scanf("%d%d",&N,&M);
    for (int i=1;i<=M;++i)
        scanf("%d%d%d",&x,&y,&c), H.ins(mp(c,mp(x,y)));
    for (int i=1;i<=N;++i)
        T[i]=i, rang[i]=0;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    Load_Data();
    while (!H.empty())
    {
        pair< int,pair<int,int> > X=*(H.begin());
        int Cost=X.first, A=(X.second).first, B=(X.second).second, tA=tata(A), tB=tata(B);
        H.erase(H.begin());
        if (tA!=tB)
            {
                Sol.pb(mp(A,B));
                Cost_Final+=Cost;
                Reuneste(tA,tB);
            }
    }
    Write_Sol();
    fclose(stdin); fclose(stdout);
    return 0;
}