#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, i, j;

vector<pair<int, int> > V[400005];

vector<pair<int, int> > VS;

vector<pair<int, int> > RASP;

vector<int> APM;

bool cmp(pair<int, int> i, pair<int, int> j)
{
    return V[i.first][i.second].second < V[j.first][j.second].second;
}

int solve()
{
    int i, j = 0;
    for(i=1;i<=M;++i)
    {

        j = 0;
        for(vector<pair<int, int> >::iterator it=V[i].begin();it!=V[i].end();++it)
        {

            VS.push_back(make_pair(i, j));

            ++j;
        }

    }

    sort(VS.begin(), VS.end(), cmp);

    APM.push_back(0);

    for(i=1;i<=N;++i)
        APM.push_back(i);

    int k = 0, cmin = 0;
    i=1;
    while(k < N - 1)
    {

        if(APM[VS[i].first] != APM[V[VS[i].first][VS[i].second].first])
        {

            ++k;
            cmin += V[VS[i].first][VS[i].second].second;

            RASP.push_back(make_pair(VS[i].first, V[VS[i].first][VS[i].second].first));

            //cout<<"["<<VS[i].first<<","<<V[VS[i].first][VS[i].second].first<<"] ";
            int x=APM[V[VS[i].first][VS[i].second].first];
            int y=APM[VS[i].first];

            for(j=1;j<=N;++j)
                if(APM[j] == x)
                    APM[j] = y;
        }

        ++i;
    }

    return cmin;
}

int main()
{

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin>>N>>M;

    for(i=1;i<=M;++i)
    {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        V[A].push_back(make_pair(B, C));

        V[B].push_back(make_pair(A, C));
    }
/*
    for(i=1;i<=M;++i)
    {
        for(vector<pair<int, int> >::iterator it=V[i].begin();it!=V[i].end();++it)
            cout<<it->first<<" - "<<it->second<<" ; ";
        cout<<endl;
    }
*/
    cout<<solve()<<"\n"<<N-1<<"\n";

    for(vector<pair<int, int> >::iterator it=RASP.begin();it!=RASP.end();++it)
        cout<<it->first<<" "<<it->second<<"\n";
//cout<<V[1][1].first;
/*
    for(vector<pair<int, int> >::iterator it=VS.begin();it!=VS.end();++it)
        cout<<it->first<<" "<<it->second<<" = "<<
    V[it->first][it->second].second<<endl;
*/

    return 0;
}