#include <fstream>
#include <algorithm>
#define nmax 200100
#define mmax 400100
using namespace std;

struct edge{int x,y,cost,k;}Edge[mmax];
int N,M,Answer,Apm[nmax],V[mmax],T[mmax];

int Dfs(int Nod) {

    if(T[Nod]!=Nod)
        return (T[Nod]=Dfs(T[Nod]));
    return Nod;

}
bool compare(int A,int B) {

    return Edge[A].cost<Edge[B].cost;

}
void solve() {

    int i,A,B,Nr;

    for(i=1;i<=M;i++)
        V[i]=T[i]=i;

    sort(V+1,V+M+1,compare);

    for(i=1,Nr=0;i<=M;i++) {

        A=Dfs(Edge[V[i]].x);
        B=Dfs(Edge[V[i]].y);

        if(A!=B) {
            Answer+=Edge[V[i]].cost;
            Apm[++Nr]=V[i];
            T[A]=B;
            }

        }

}
void read() {

    int i;
    ifstream in("apm.in");
    in>>N>>M;

    for(i=1;i<=M;i++) {
        in>>Edge[i].x>>Edge[i].y>>Edge[i].cost;
        Edge[i].k=i;
        }

    in.close();

}
void write() {

    ofstream out("apm.out");
    out<<Answer<<'\n'<<(N-1)<<'\n';

    for(int i=1;i<N;i++)
        out<<Edge[Apm[i]].x<<' '<<Edge[Apm[i]].y<<'\n';

    out.close();

}
int main() {

    read();
    solve();
    write();

    return 0;

}