#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
#define mp make_pair
#define pb push_back
#define INF 10000000
using namespace std;
int D[200001], Use[200001], T[200001], Total=0, i, N, M, x, y, cost;
vector < pair<int, int> > G[200001], Sol;
pair <int, int> Y;
inline void DF(int x)
{
    int Min, nod;
    pair<int,int> y;
    for (i=1; i<=N; i++) D[i]=INF;
    for (vector < pair<int, int> >::iterator it=G[x].begin(); it!=G[x].end(); it++)
        y=*it,D[y.first]=y.second,T[y.first]=x;
    Use[x]=1;
    while (1)
    {
        Min=INF;
        nod=-1;
        for (i=1; i<=N; i++)
            if (!Use[i] && Min>D[i]) Min=D[i],nod=i;
        if (Min==INF) break;
        Use[nod]=1;
        Total+=D[nod];
        Sol.pb( mp(T[nod], nod));

        for (vector< pair< int, int> >::iterator it=G[nod].begin(); it!=G[nod].end(); it++)
        {
            y=*it;
            if (D[y.first]>y.second)
            {
                D[y.first]=y.second;
                T[y.first]=nod;
            }
        }
    }
}
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(y, cost));
        G[y].pb( mp(x, cost));
    }
    DF(1);
    printf("%d\n%d\n",Total,N-1);
    for (vector < pair<int, int> >::iterator it=Sol.begin(); it!=Sol.end(); it++)
        Y=*it,printf("%d %d\n",Y.first, Y.second);
    return 0;
}