#include <cstdio>
#include <vector>
#include <set>
#define INF 2000000
#define pb push_back
#define Nr 200001

using namespace std;

int i, N, M, Total=0, D[Nr], U[Nr];
vector < int > Sol;
vector < pair < int, int > > G[Nr];
set < pair< int, int > > H;
inline void read()
{
    int i, x, y, cost;
    scanf("%d%d", &N, &M);
    for (i=1; i<=M; i++)
    {
        scanf("%d%d%d", &x, &y, &cost);
        G[x].pb( make_pair(cost, y) );
        G[y].pb( make_pair(cost, x) );
    }
}

inline void solve()
{
    int i,nod,cost;
    vector <pair<int, int> >::iterator it;
    for (i=2; i<=N; i++) D[i]=INF;
    H.insert ( make_pair (0, 1));
    while ( H.size()>0)
    {
        nod=(*H.begin()).second;
        cost=(*H.begin()).first;
        H.erase( *H.begin());
        if (U[nod]) continue;
        U[nod]=1;
        Total+=cost;
        Sol.pb(nod);
        for (it=G[nod].begin(); it!=G[nod].end(); it++)
            if (!U[(*it).second] && D[(*it).second]> (*it).first)
                D[(*it).second]=(*it).first, H.insert( make_pair(D[(*it).second], (*it).second));
    }
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    read();
    solve();
    printf("%d\n", Total);
    printf("%d\n", N-1);
    for (i=1; i<Sol.size(); i++)
        printf("%d %d\n", Sol[i-1], Sol[i]);
    return 0;
}