#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define INF 999999999
using namespace std;
vector<pair<int, int> > G[200001], Sol;
multiset<pair<int, int> > H;
int i, N, M, x, y, cost, Total, T[200001], D[200001], Use[200001];
void PRIM()
{
    while (!H.empty())
    {
        set<pair<int, int> >::iterator X=H.begin();
        int Nod=(*X).second, Cost=(*X).first;
        H.erase( X );
        if (T[Nod]!=0) Sol.pb(mp(T[Nod], Nod));
        Use[Nod]=1;
        Total+=Cost;
        for (vector<pair<int, int> >::iterator it=G[Nod].begin(); it!=G[Nod].end(); it++)
            if ( (*it).first < D[(*it).second] && !Use[(*it).second])
            {
                if (D[(*it).second]!=INF) H.erase(H.find(mp(D[(*it).second],(*it).second)));
                T[(*it).second]=Nod;
                D[(*it).second]=(*it).first;
                H.insert(mp(D[(*it).second],(*it).second));
            }
    }
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for (i=1; i<=M; i++)
    {
        scanf("%d%d%d", &x, &y, &cost);
        G[x].pb(mp(cost, y));
        G[y].pb(mp(cost, x));
    }
    H.insert(mp(0,1));
    for (i=2; i<=N; i++) D[i]=INF;
    D[1]=0;
    PRIM();
    printf("%d\n%d\n", Total, Sol.size() );
    for (vector<pair<int, int> >::iterator it=Sol.begin(); it!=Sol.end(); it++) printf("%d %d\n", (*it).first, (*it).second);
    return 0;
}