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

#define mp make_pair
#define pb push_back

using namespace std;

const int Mmax = 400005;
const int Nmax = 200005;

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

int N, M;

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));
    }
}

int sum;

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

    int cnt=1;
    bitz[1]=1;

    while(!Q.empty() && cnt<=N-1)
    {
        int c=-Q.top().first;
        int dad=Q.top().second.first;
        int nod=Q.top().second.second;
        Q.pop();

        if(bitz[nod])
            continue;

        cnt++;
        bitz[nod]=true;
        sum+=c;
        muchie.pb(mp(dad,nod));

        for(it=G[nod].begin(); it!=G[nod].end(); ++it)
        {
            if(bitz[it->first]==0)
                Q.push(mp(-(it->second),mp(nod,it->first)));
        }
    }
}

void Print()
{
    printf("%d\n", sum);
    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();
    Prim();
    Print();
    return 0;
}