#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>

#define pb push_back
#define mp make_pair
#define dp pair < int, int >

using namespace std;

const int Nmax = 200005;

int n,m,val;

vector < pair < int, int > > G[Nmax],muchie;
priority_queue < pair < int, pair <int,int > > > Q;
bitset < Nmax> bitz;

void Read()
{
    scanf("%d%d", &n, &m);

    for(int i=1; i<=m; ++i)
    {
        int x,y,c;
        scanf("%d%d%d", &x, &y, &c);
        G[x].pb(mp(y,c));
        G[y].pb(mp(x,c));
    }
}

void Solve()
{
    for(vector<pair<int,int> >::iterator it = G[1].begin(); it != G[1].end(); ++it)
        Q.push(mp(-(it->second),mp(1,it->first)));

    bitz[1]=true;
    int nr=1;

    while( nr<n )
    {
        int dad,nod,cost;
        cost=-Q.top().first;
        dad=Q.top().second.first;
        nod=Q.top().second.second;

        Q.pop();

        if(bitz[nod])
            continue;

        bitz[nod]=true;

        ++nr;

        val+=cost;
        muchie.pb(mp(dad,nod));

        for(vector<pair<int,int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
            if(!bitz[it->first])
                Q.push(mp(-(it->second),mp(nod,it->first)));

    }

}

void Print()
{
    printf("%d\n", val);
    printf("%d\n", n-1);

    for(vector<pair<int,int> >::iterator it = muchie.begin(); it != muchie.end(); ++it)
        printf("%d %d\n", it->first, it->second);


}

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

    Read();
    Solve();
    Print();

    return 0;
}